I recently found and registered a 6 letter .com domain on godaddy: http://Shaloc.com, the site is mainly for Location Sharing, SHAare-LOCation = SHALOC, this is one way to find .com domains, the word may not mean anything, but based on what the site does it can be made easy to remember.
.COM is definitely better and easy to tell others about it.
Suggestion: make a "random" mode (ie, random participle and location for each of the 5 suggestions) and default it.
My take on the .com vs. not: do both (ie, shoely.com and shoe.ly)... not like it's a significant cost. The .com is essential because some browsers still auto-default that extension.
Pair up these three and I think we're all set: http://impossibility.org/ https://domize.com/ http://nxdom.com/
I actually wrote a tool to solve this problem (it finds short, available .coms using real words):
http://impossibility.org/
Ironically, it's a .org :)
Basically, the reason you want a .com is so people will know you're a website. It's instantly parsable. "I work for Shoes.com" vs "I work for Shoe.ly... it's a website that sells shoes". It greatly simplifies advertising, press coverage, word of mouth, etc.