1. letterboxing is there for a reason
2. If you're uploading it to youtube, then the letterboxing will come back if you didn't get the aspect ratio right
3. http://www.lwks.com/index.php?option=com_docman&gid=8&task=cat_view&Itemid=189 is the best free non-linear video editor on Windows. That said, for basic editing like removal of letterboxing, avidemux, virtualdub, and Windows Movie Maker are more than capable.
I prefer the adobe products for video editing.
Adobe Premier and After Effects are very nice though have somewhat of a learning curve if you are new to adobe products.
A lot of my friends use Sony Vegas Pro.
A learning curve isn't a problem IMO. All non-linear video editors have a learning curve. It just comes with the territory.