Ok, I noticed people making lots of suggestions. Here's what I have to say.
In order to think of something realistic for Notch to implement, it needs to be simple. If you add an entirely new dungeon idea or bird egg blocks that would be going too fast in one update. It just doesn't seem like Notch would do that.
Let the Mojang team make large bounds like that.