Ohhhhh man, I've been waiting for one of these threads.
Stand aside, everyone, I make large posts!
1) Some way to incorporate new and upcoming terrain/blocks into the server, e.g. jungles and the upcoming emerald ore. Since the plan of making a new map has (happily, IMO) been scrapped, I think the best way to approach this would be with a map expansion. I'd like to see a modest
increase in map size (say, 1000 blocks on each side, for a total size of 7000x7000), while leaving open the possibility of doing the same thing again (e.g. going to 9000x9000) at some distant future time when even more features are added to Minecraft.
A single large expansion in the near future would also be an option, and might be preferable for those who preferred a map wipe. If this is done, though, ensure there's a plan to deal with future content. One such strategy would be to say that the expanded region is expendable and is not to be treated as permanent (e.g. the outer rim of the map could be wiped at a future time to make way of new features--players can go there to seek resources, but shouldn't build large structures there).
A variation on the expansion would be to make it all in one direction (e.g. instead of adding on area around the perimeter of the map, put the entire new area on one side of the current map). This has the advantage of letting players travel a greater distance from the map's center before reaching the new boundaries (nice for those who wanted a map wipe), but would have the disadvantage of making the new territory more easily accessible to some players than others, depending on where they live in the current map).
This possibility was not my original idea--I saw someone else post it on a different thread here, but don't remember who it was. Props to whoever it was.
An alternative to expanding the map would be to do another public realm wipe. I consider this to be a less attractive option, though, since it causes the sharp cliffs and square islands that so many players complained about after the last public wipe. If this option is taken, I'd encourage the staff to be more strict in enforcing the rule that realm owners must "smooth out" the edges of their realms within a certain timeframe.
2)
Multiple spawn cities. The idea is a bit more fleshed out in
this thread by Doc H, so I won't go into too much detail on that point. The only thing I'd like to add is that, if both this idea and a map expansion are implemented, it would be good to have a spawn point out in a new distant area; this would work best with the idea of a single large new area being stuck on to one side of the map, as players interested in a fresh start could travel out there and have it as their spawn point.
3) I'd like to see some kind of
automated shop system. If this is implemented, it wouldn't necessarily have to undermine the legit nature of MineRealm; as long as the items for sale are provided by a player rather than being generated out of nowhere, this would be a perfectly legit system. There could be some incentive to use player-owned stores throughout the map (read: to travel throughout the map and see new parts of the world) rather than relying on /trade; for example, player-owned stores could have a reduced sales tax, making them able to successfully compete with players who go to /trade. I don't have the technical expertise to suggest how exactly a shop would be operated, but based on what I've seen in the mods section of the minecraft forums, it seems like left/right-clicking on signs is the usual way of doing it. No reason not to do something more unique though, if Intelli's up for a bit of programming-based wizardry.
I think that's about it. For now. I'll let you know if I think of anything else

The Greymarch has ended.