I browsed youtube to see what other Android users liked as far as apps/widgets when I bought my first android phone. Another good way to find stuff is to browse the market on the website by category of apps depending on your interests. There are a lot of hidden gems!
as stated, very personal.
love the Market as i have downloaded tons of apps, and deleted the ones I didnt like.
download and try them.
i'm new to android too (from crackberry) and love this new phone, and android.
my fav apps: facebook, craigslist, appbrain, usatoday, 2x battery.