I'm a big proponent of brainstorming while walking. If I hit a mental block while programming, writing, or doing some other sort of critical thinking/creative exercise, I'll just drop everything and go on a 30 minute stroll. I'll either end up solving my problem or getting some exercise, so either outcome is good.
On the other hand, I have a mathematician friend who's a big proponent of shower brainstorming. We still give him crap for the day when he was working on a proof and took a two hour shower.
