What would you like to see in a 4e combat map, what features, where should it take place etc etc?
I'd say it needs large spaces and interesting terrain. Places to push, pull or slide people onto or over. Difficult terrain areas to slow people down and chokepoints that you can draw people into before hitting them with a fireball. Limiting angles of attack helps structure combats with diferent monster types as well. A big open field will result in your artillery monsters being taken out by a fast striker, but if you have a river with two tree bridges your brutes/soliders can hold the tree bridges whilst the artillery blasts from the other side of the river.
Definately areas with cover and areas that limit where people can move. It makes them think more tactically and not just a big static fight them in the middle type of area.
I'm working up some battle maps now, also. I would second everything said so far, and add: objects that provide for interactivity. For instance, statues that can be pushed over on a strength check, or tapestries that conceal a trap. I'm making a roadside map right now with a shrine to Avandra that could have an aura that conveys a bonus.
Nice ideas all ... I especially like the interactive elements, though it does require (or would at least be nice) that you map the effect of what you did also for a map overlay - for instance a broken statue taking up some squares.
Also like the bonus squares, when I, as a player, see a pentagram - I always wonder if it conveys a bonus to an evil caster standing in it...
I always like to add "long-forgotten" traps and puzzles so the players can use their imaginations.