The world is auto generated typically, within the parameters of Flat and Normal, but you can get some plugin's to influence the type of world beyond that.
Phoenix is one such mod. If we build the world using Bukkit plugins, then we can easily migrate it wherever we need - it is just a folder located in the server directory and a couple lines in the config file.
I think the main thing is that you need as client side mod as well as a server side mod, and that is a bit tricky to do, but I am sure we all could manage. I don't know if a normal hosted solution would give us access to the files we need for a direct server jar mod though, as most are set up to support Bukkit plugins, which don't alter the server jar file at all.
There seems to be a plugin,
SpawnArea, that will allow us to generate random spawns, so we could play with that to test things.