After the great feedback I got from this post, I just wanted to let everyone know that I just completed the Pretty Link bookmarklet -- it's available right now in the 1.4.11 release. Here's my blog post that talks about it:

Create Short URLs on the fly with the Pretty Link Bookmarklet

I'm working on a Firefox sidebar that will be even better ... but that will take a bit longer to complete :) ...