You know, you are probably right about Gideon. Almost all of the campaigns I play are against my wife, and we only play two characters. A legendary Gideon is insane, but one with normal health/activation count probably not too broken.
I played Gideon and Davith together in Bespin and was an absolute nightmare for my wife to deal with. Won't ever do it again. :-)
That indeed sounds like a pain. I usually run 4 heroes no matter what. Even if that means a player controls multiple heroes. I feel that the game is just more balanced that way.
Playing more than two heroes per playing is kinda rough.