Stiff-soled shoes tend to be the most comfortable.
If they are not SPD cleats, you can just get some good quality platforms, and forego the cleats for now, though the pedals I linked to do not require cleats.
There are many threads here on pedals.
Thank you so much for all the information I am going to put on the platform pedals and get on the road!