We use heroscape tiles for our battles, which can take a few minutes to setup since you need to snap them together. Sometimes if there is a quick encounter I'll just put the mini's on the table and just estimate distances.
I used to not use minis at all, but I actually found that even though minis make the setup take longer they make up for it by speeding up the rest of the combat. With no minis my players were constantly asking "How far away is X" or "Will a line hit X and Y?" etc. Also, I'm running a game with 8 players right now so there are just too many guys in combat to keep track of in my head sometimes.