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.
bike pedals unscrew in a fun way!
One thing to note about bike pedals is that one is regular thread and one is reverse thread. The reason for this is that as you pedal, your left foot would naturally be unscrewing the pedal if it were a regular thread. The story goes that the Wright brothers encountered this problem first and created reverse threads. So, the one thing that I finally learned in the process was that you should read (and re-read and re-read) the Park website about this process. Left pedal, reverse thread. Right pedal, regular thread.
A real pedal wrench
Because I had tried to unscrew in the wrong direction so many times, I couldn't unscrew them in the normal direction with our regular wrenches. That's when I learned the second lesson of the process: buy a real pedal wrench. If you take your bike in to the shop they are going to charge you around $10 per bike for a pedal change. If you like biking enough to get specialized pedals you are probably going to do this more than once in your life: buy a specialized pedal wrench for $20. The pedal wrench is about twice as long and tapers from a nice big thick soft handle down to the skinny 15mm & 9/16" wrench that you need for most bikes.