I'm terrible at walking w/o a destination in mind. A while ago I made this crappy little web tool to give me a random destination to meander to: http://roust.sknkwrks.net/
Not meant to be hostile, genuinely curious.
The other part is that I fall into patterns really easily. If I don't have a set destination in mind when I leave my apartment, I often just end up at the subway stop I take to get to work.
Pick a destination, but vary the route. Don't take the optimal route. It's easy on grid streets; just move laterally a block or two on the way. And give yourself permission to explore, by making sure you don't have anything planned: just stop and poke your nose into anything that sparks your interest.
For instance to find a nice cafe you've never been to before, or a nice bookshop.