I've been hunting for decent lentils since returning to Australia. In London I used to buy the lovely Puy Lentils (lentilles vertes du Puy) which are amazing green lentils. The key is that, unlike other varieties of lentil, they don't fall apart when cooked but actually manage to keep their texture. I use them a lot in stews and the like.
Today I discovered my local deli in Marrickville Metro has this type of lentil. They're a little more expensive than most lentils, $5/kg, but well worth it. Yummy!
Currently in the oven is a casserole of Italian sausages, onion, carrot, garlic and green lentils. We're gonna eat well tonight.