I also wouldn't mind a bi-cameral system in which the regional governors...or people that they nominate...form an "upper house" of some sort.
The prospect of an appointed house of legislature sounds intriguing. It would make the Governorships much more important, though it would also allow for incompetent legislators being appointed due to party politics.
Maybe every two months the citizens of that region could vote in an up-or-down referendum on the appointed legislator; getting more downs than ups would require the Governor to appoint a replacement.