It's worth sitting down and methodically thinking through how you plan to use this over the coming year or so, and make an actual (not mental) list. Then compare that list to sites you may look at and do trials for. Many of these sites have great "first impression" paths for new users, where you get quickly lost in the glitz and easy features. Only later will you realize some core feature you really wanted may be absent.
As a few examples: Do you want the ability to have private galleries, e.g. for different friends or different family, that ones may not want to see? Do you want a site where people can buy your photo as a print, or merchandise like tee shirts (I'm not saying where you make money, necessarily, but simply where they can hit a few buttons and get a coffee cup with that photo). How will does it look on cell phones and tablets (and do you care)? Are you hoping it will also be a backup for your photos (ability to store raw, to store full resolution, and whether the site munges your data may be relevant here)? Do you care if the site strips your metadata (your name or copyright)? How will you want to organize your site (this is often hard to envision when first starting, but think a few years down the road and ask how people will find things), and does the service offer such organizing tools? When (not if) something goes wrong, do they have good support (look for a user-to-user site, and read their forum posts)?
Personally I love free but found that cheap was better, and use Smugmug, but there are a LOT of choices. Do not rush into a choice, try out a bunch, almost everyone has free trials.
Postscript: Look for sites that have publishing plugins for Lightroom, it will greatly simplify your life.
