You already mentioned them, but I’m a huge fan of lentils. They go with so much stuff and you can combine them with a variety of spices. Give me any leftover ingredients and some lentils, and I’ll cook up something delicious. I can and will eat lentil soup for days.
They are also a pretty solid crop, they can grow in a variety of climates, require little water and are good for the soil.