I'm gonna kick myself for suggesting this template because I still feel like I have a lot to learn on it, but I think Strategic Greece is a wonderful template for separating more skilled players from less skilled players. See
http://warlight.net/MultiPlayer?TournamentID=7185 for an example tournament.
My favorite template ever is probably guiroma. It's got great gameplay and most players are at least familiar with the map. See
http://warlight.net/MultiPlayer?TournamentID=5176 for a good tournament with mostly high quality players.
Both the above templates are 0% luck straight round... if you want 16% weighted random, I think East Asia & Oceania is a good map/template. Despite much of the map not getting used (the islands to the northeast are usually worthless), it has a nice combination of chokeholds and wide open space that can result in really interesting gameplay. See
http://warlight.net/MultiPlayer?TournamentID=8533 for a tournament in progress with high quality players.
Finally, I'm not going to suggest this template, but simply mention an idea that Nich implemented: random cities distribution, neutrals of size 10, and lots of wastelands of size 2. The idea is that you get a layout that resembles random warlords, but some territories have multiple picks available while others have none at all. Makes for an interesting game. Here's an example of this idea applied as a variation on Heavy Earth:
http://warlight.net/MultiPlayer?GameID=5046550 . I'm not a big fan of heavy earth but I wonder what this would do to the standard medium earth template?
I could provide a lot more suggestions but I think this will do for now ^^;