I'll add in a few tidbits:
- arches: perhaps the shoes/pedals do not offer enough support and the muscles supporting the arch are not up to it. In general, stiffer and more support is better. Also, if they abnormally flat/high arched feet, there may be a poor fit with the shoes regardless of stiffness.
- elevate legs to accelerate recovery. Lay back on the couch and get your legs up on some cushions. Warning: side effects may include napping.
- Stretch consistently to maintain flexibility... and look for stretching routines that target a range of muscles instead of just touching your toes and calling it good. Studies have shown that stretching just before you exercise doesn't help that much, and in some cases can increase risk of injury. However, consistent stretching to maintain flexibility is good. Just don't expect to stretch a few seconds just before hopping on the bike and expect it to be a cure-all.
- if you are having bike-related issues and are planning on stacking on the miles, then a bike fit can be a good idea. The quality of bike fits varies pretty widely so you might ask around on a local bike board for recommendations. There is a *HUGE* difference between a quickie fit at a bike shop and an actual fit where they really look at measurements, check body alignment through a pedal stroke, etc, and it is typical for a good bike fit to cost between $100 and $200. It is not uncommon for the fit to conclude with a recommendation for a different length stem or other bike bit. If you go to a PT for the fit, it may be at least partially covered by insurance.