For uncivs Japan, Persia and Egypt could be fun. The former two have event chains to civilize them and Egypt is quite strong to start with. If you manage to trash the Ottomans and keep the British out you're set for early civilizing. Haven't tried it myself, though.
Sweden can be a fun country. Support the Danes in their wars against Prussia and Austria by landing troops in Prussia and occupying Berlin ASAP. Then you're set for Scandinavian Unification and can even grab parts of Northern Germany. If you help out Austra in the Seven Weeks War you might prevent German Unification and can go on making the Baltic your lake. Russia likes to sell Finland and other non-cores.
Another fun game I had was as moderately expansionist Brazil. In VIP it is not that difficult to get a strong foothold in Africa if you don't mind losing a bit of prestige through an early DoW. By the time of the ACW you can be quite a powerhouse and after that you might want to grab an immigration-swelled Uruguay. You probably won't be tech leader at any time, but it can still be a lot of fun.