Pain on the sides of my feet
Shoe fit and the stiffness of the last are the first things that come to mind.  I'm thinking you have a wide foot and cycling shoes are typically on the narrow side.  

I've always had major issues with any shoe that was slightly too narrow for my foot.  I'd get cramping along the outside edge of my foot. It gets worse when the shoe becomes stiffer (It's just hell for me to wear X-country ski boots or hockey skates).  As cycling shoes are meant to be something akin to a block of wood, that means for me I need to be certain the shoe isn't too narrow or I'll be in pain really quick.

For my road shoes, the size is such that I actually have a slight amount of heel slippage which allows my foot to flex a bit more than what typically would be expected.  With my Mtb shoes, I go for the freeride type of shoes which don't give nearly the same amount of energy transfer but my feet are way happier at the end of the day.

I had a pair of Sidi shoes a few years back (Awesome construction) but found that even the Wide width was narrow and caused me pain after a few hours of riding. Specialized seem to fit narrow as well.  I've had to try on many a shoe to find a wide enough fit and usually I'm still left with having to go sockless just for a little bit extra comfort.

Get your foot sized by an expert and go from there.  If it's a width thing you'll know with numbers.  If it's something else then you can start to narrow things down.