Some badly designed classes like Monk, Paladin or Knight are still going to suck, but not so hard as if they were hitting the mid levels and beyond.
I'd probably still go for partial gestalt to give the weaker classes a boost, or turn it into a full-hog gestalt game where after the first six single-class levels have been gained, the levels are turned into gestalt levels one at a time before extra feats are given out after level 6//6.
Oh yeah, that's a good idea.
Pal/Mon would be something potentially fearsome, though. Grab yourself a flurry weapon and smite away while having ridiculous saving throws. Stats are spread a little thin, though. Probably better to just couple with something else.
I don't know if I've played an E6 game (E7 in Pathfinder), but it definitely seems like a decent way to help balance things. Unfortunately, even at that level, you can see the potential of casters start to outshine pure melee classes (fireball and fly, both third-level spells, are both pretty big deals), but it's manageable at that level. 5th level also gives casters the potential to start crafting wands; with scrolls and wands available, they could, with time, have their entirely library of third-level spells available to them on a whim, which definitely has the potential to warp the balance between PCs.
That said, I wouldn't mind such a low-powered game, and it's great that some more fleshed-out rules and the like have been developed here.