Really, natives aren't very fun.
Do the americas ever try to revolt? And if they do, can you just take control of them?
Sometimes they do. And yes, you can control anyone. ANYONE, although rebels requires a console command.
My suggestions for who we should choose from:
Scotland - Try to form Great Britain, then keep France and Burgundy from getting too strong, while racing the Iberian powers to the New World.
Morocco - Inferior technology, lots of useless desert to expand into, and frequent wars with the Iberian powers.
Ottoman Empire - Kill the Europeans!
Some German two Provence minor - Rise above petty squabbles over our dead enemies, then form Germany a few centuries early.
Muscowy - Stave off the Golden Horde until we can annex Novgorod and form Russia! Then try to become a massive giant and kill everything.
Holland - Avoid being killed by large, extremely hostile neighbors.