We got new pedals for our bikes (road and mountain) and installing them was a real pain in the ass.
Attempt one - regular 15mm wrench
I didn't have a good 15mm wrench, so we went to the bike shop and they had pedal wrenches and regular wrenches - the regular wrench set was on sale so we got that. I think at that point I just got lucky because I got the pedals off of my road bike - great. Then I started working on Nikki's road bike and had no success.