I'd really like an Unreal-style walk key that stops you from falling off edges when you get too close to them. That way when you are building off the side of something you don't have to be really careful to position yourself just right so you can still build and not fall. Have the option to set it as a toggle too, some of us like having our walk keys as a toggle instead of something you have to hold down.

That's a cool idea! I think this would really cut down on the frustration of repeatedly falling off your buildings when you need to construct something like a bridge, without hurting the feeling of "immersion" you have because, for example, you can't fly around like you're in an editor.
I tend to erect huge poles that reach to the maximum build height around where my builds are so I can find them from anywhere. Bookmarks would probably be a more elegant way of finding things though. Or as I said before just have your coordinates outputted to the top left so you can write down where stuff is done or just stick it in a text editor if you don't have a pen handy.
I think it would work best if you could simply designate a "first spawn", so that whenever someone, or you yourself, load up the level, you will spawn at that specific point. With that you could actually have players spawn underground and then find there way out of a creepy dungeon or so, with a great feeling of relief once the exit to the sunny outside world is found

And apart from that there'd only have to be those teleport bookmarks, preferably the way
Zolyx suggested it, similar to Exile.
Maybe with these things added the currently random and pretty unhandy respawn function could be left as it is, for example to still quickly scan the whole world for specific places.
Quite a lot of great ideas here so far!
Minecraft is quite the click-o-rama. I'd like to have an option to 'hold' block removal (and/or placement) i.e. holding the right mouse button would make you remove blocks until you let go. Alternatively something like shift+RMB to continuously destroy blocks.
Good idea. I'm actually already using one of my keyboard's macro keys for a function like this. I can simply press a key to toggle "rapid fire", which doesn't do more than just spam left click about 50 times per second. That really helps

I guess there should be lots of little programs which let you do that using any key, but a built-in function for Minecraft would be great, of course.