4th Edition, from experience
When inflicted on a 4e group as part of a curse, it gave everyone a headache and made combats incredibly long.
The hex based map presents incredible difficulties in calculating zones relative to the ease of calculating zones in a square map. Either zones in a hex grid are the same area as a square grid or they are the same approximation of a circle. Both have their difficulties in calculation. I found that with a group experienced in square maps, everyone had to rebuild their standard tactics from the ground up to deal with the different terrain.
On the advantages side, a hexagon approximates a circle far better than a square, and with wire templates, the difficulty in calculating zones will be reduced. It also offers odd cognitive dissonance (as observed) with the squiggly-lines problem: moving "across the grain" of the map will have a character rapidly oscillate between two different rows, annoying some players.
In the question of balance, bursts will generally effect fewer people (close burst 1 has max 6 targets instead of 8) and blasts may or may not effect more people, depending on how you calculate the area of the blast. A hex-diamond-shaped blast will offer a player greater "reach" than the normal game's blast, at the expense of "width" simply by the geometry of the hexes. Changing the definitions of blasts and bursts to be more "realistic" may help the problem, but will introduce non-trivial balance problems in both directions.
My general recommendation is to never inflict a hex grid on a group used to square grids, but it may not be a bad basis for a campaign if everyone wants a hex grid. It's probably more appropriate to use it with a simulationist system though.
3.5 from little experience
While running and playing in some play by post versions of 3.5, we tried using hexes. While 3.5 maps more ably to hexes because it's based on naturalistic geometry, the heuristic for calculating distance is slightly more difficult than "every other diagonal counts as 10 feet. Still, hexes are not a bad choice for 3.5 especially if using house-ruled ideas about facing.
Other tactical games
Fundamentally speaking, if a game is designed for real geometry it will play well with hexes as both squares and hexes can be mapped to circles and feet without too much trouble. A game with high amounts of abstract tactical design "baked in" (4e) will do less well, because much of that tactical design is based around assumptions of a square grid.