Encapsulated with Nomads on is a lot of fun.
Personally, I like Honeycomb (after the per-planet turrets
) because you've got a mix of high-connectivity and isolation, depending on seed and size.
When I was learning, I played the X and Maze maps a lot (very easy to make amazing Whipping Boys).
Cluster was great before the per-planet turrets - and is still good - but I think Honeycomb makes for more interesting maps, especially if you don't show all stars at the start.
I never play Snake, though. Games just take way too long.
Before auto-untangle, the Vines and similar maps were unplayable to me. Now, I can play them, but they suffer a bit from Snake syndrome (30 and 40 hops distances between AI worlds, etc).