Legendre
Chieftain
France is probably my current favorite for the 600AD start (using the Pacifist-Breme-Squatting-Technique PBST!), but my first UHV victory for that start was with the Dutch. As long as you keep Amsterdam relatively defended and don't get exiled (like me!) you can focus on your UHV goals which gives a different feel than playing for your UHV with Russia and just doing what you would normally do. Both Portugal has a similar feel, but I find it's UHV req for all the open borders agreements to be kind of annoying.