Is millet similar to lentils?
Millet is a small sized grain, and has a pretty mild, bland flavor. Lentils are legumes, and have a little bit more flavor to them. 
To me the two things do not taste similar, but I guess that is a matter of opinion. 

In some urban areas in the US, you can often find whole grain millet in food stores which have a "health food"/"organic" type orientation.