That, but it also costs me a lot of time to set up and tear down our database. If I had to do that for every test everything would slow to a crawl.

If you can reuse the test db then it's still not order dependent. If your test framework doesn't support reusing setups, you create some kind of function like getOrCreateDbConnection() that idempotently set up your test environment.

Order dependent tests happen when you have like a createUserTest and a deleteUserTest and the latter doesn't actually create the user it deletes but requires being called strictly once after createUserTest.

Some of our code at work is like that and it's a pain because it means the tests have to run sequentially (slow), you can't run any single test in isolation and if something breaks it sometimes causes a failure in the wrong test.

I try hard to mock out the database calls. I know some disagree, but I'm pretty productive and the occasional bug that does slip through because of this is worth the time saved, IMO.

don't tear down the entire db for each test, make utilities that create the base objects you need to operate on and chain them together

Absolutely agree with you here.