I recommend mushrooms (dried wild for best flavor) and kasha (toasted buckwheat) to deepen the flavor of lentils. If you want an extra smokiness, there's a spice called kala jeera (sometimes called black cumin, I think) that's really lovely.

This soup, from the New York Times' Martha Rose Shulman is easy, filling, healthy, and so delicious: http://www.nytimes.com/2008/12/30/health/nutrition/30recipehealth.html

Thanks for the reminder of Deborah Madison's Lentil Minestrone. That' is a great recipe. I found it online in a good blog post:
http://lifedivided.blogspot.com/2010/01/deborah-madisons-lentil-minestrone.html

A lot of people (me included) like this one, which will be in the first food52 cookbook: http://www.food52.com/recipes/2348_lentil_and_sausage_soup_for_a_cold_winters_night I made it the night before last, using brown instead of French green lentils, white instead of red wine, and chard instead of spinach. It was tasty! ;o)

Check out the Lentil Minestrone in Deborah Madison's Vegetarian for Everyone.

Always put in a Parmesan rind if you can!

If you don't mind a bit of bacon in it, this is my current favorite for using small firm french or beluga lentils:
http://www.food.com/recipe/potage-aux-lentilles-et-aux-lard-lentil-bacon-and-tomato-soup-248085