I think the classic CLR text is great but, yeah, caches through quite a monkey wrench into naive big O analysis.

Still, I think the time investment to learn algos and data structures isn't too much of a burden.