I guess it would be helpful to start discussing this now. I am thinking of something which combines the following stats and filter mechanisms. I haven't really thought through how it will work in practice so this is an idealized view of what it would allow you to sort / filter on.

Automated / Mechanical Stats

Most popular by number of games played per day / week / month / all time
Board size (some multiple of territories / borders to automatically calculate this) 

Player Stats

Top rated (i.e. by the board rating system)
Most favorited (i.e. by how many people have made the board their favorite) 

Filters - used to restrict what is visible in the board list

Designer
Number of Players
Size (number of territories)
Simultaneous vs Regular
Teamplay
Default Fog
Duel maps (i.e. 2 player boards)
Release date 

Tags - another way of filtering what is visible in the board list

Abstract
Arcade
Classic
Duel
Fictional
Geographical
Hordes!
Terrain

Difficulty (set by review team)

Beginner
Intermediate
Advanced
Expert

I'd be a bit concerned that the Filters (and even potentially Difficulty) is going to be a bit difficult due to multiple Scenarios having what would be different sets of Filters from each other and/or the base Board.

Difficulty is going to be tough, I'd almost say wait on that if the Sorting can be completed quicker.

Still going to have Alphabetical I assume?  Enhanced Alphabetical (ie select A-E, F-K...) would be nice.

I love the idea of a Difficulty filter...very useful for new and existing players.

I also think a Difficulty Rating will be very useful.

Perhaps there could be a page/tab for every Scenario.  This might not be as unwieldy as it sounds. 

For instance, a slice of the full listing of boards might look like:

Mediterranean Mayhem!!
Micro Mission/Default
Micro Mission/Simulgear
Micro Mission/Splice
Micro Mission/Stasis
Micro Mission/Twist
Mobs of New York
Mutiny on the Bounty
...

Apply a filter for a Difficulty of n+ and you might get:

Mediterranean Mayhem!!
Micro Mission/Simulgear
Mutiny on the Bounty 

I think the page/tab for each scenario would work.  Another way would be to have a map match the filter if any of the scenarios match, and then have a 'matching scenario' column which lists all the scenarios that match.

Is there going to be a limited set of tags, or can a map be tagged with anything?  Can maps have more than one tag?

Other possible filters:

rotating vs. escalating vs. fixed card scale

Total board bonus

filters for advanced features (border modifiers, capitals, territory selection, unit placement, fortify/view borders, etc.)