Red, yellow, black and brown lentils are all good. Avoid green lentils as they work better in stews and can ruin the texture and flavor of the soup. You can even try making this soup with mung beans or lobia (black eyed peas), but you’ll need to soak them in advance.