Hey Tim. Those caps are the same. The blue one is probably an older one. Newer capacitors are far smaller than caps produced 20 or 30 years ago due to different manufacturing techniques. Normally, short-fat ones are not used unless it's for clearance issues. Just a quick note -- I would never install an old/used capacitor. They are cheap enough to NOT warrant reuse, especially electrolytic capacitors which are prone to age related failure. Inside is an electrolytic solution which dries out over time. As for polarity, yes, you MUST reinstall them in the same polarity. The PC board usually is marked with the polarity. However, you should always check and note the polarity before removing them because if you forgot to check and the board is not marked, then you are not going to have a good day unless you have some reference. BTW, if you install it backwards, it's likely to fail very quickly (since the reverse current will break down the connection inside) and if enough current passes through the cap (such as in a power supply circuit), it's likely to explode. No kidding -- watched one happen up close myself. The stripe almost always is marked for the negative lead but I have seen the stripe marked for positive too. Read the stripe carefully. The (-) legend should be visible in the stripe. Just saying don't presume, especially on the older ones. Look and read the stripe carefully.
As for solder pads not wanting to reflow -- just turn up the heat a bit or wait a little bit longer. It does take some practive go get the hang of soldering techniques. Also, the quality of your gear will make a difference. If you are using a normal pen type soldering iron, they don't heat up very fast for low wattage ones, and high wattage ones will burn off the solder very quickly and oxidize. You need to clean and re-tin the tip frequently or you won't get good heat conduction. If you don't solder on a regular basis, it's easy miss this. I know you are trying to desolder but maybe even add a bit of solder while you are desoldering -- that frequently makes it easier. Mostly though, the conformal coating and a dirty (not tinned) tip is the reason for solder not wanting to melt.
BTW, if you are planning to recap, send me a list of the caps you need and I can mail you the whole shebang, if you like. That way, there will be no recycling of old caps and you don't have to go shopping with a laundry list of caps, 1/2 of which are probably not stocked at your local supplier. I do not, however, stock any SMD's. Don't work on them frequently enough, nor do I like to work on those newer boards. My eyes can't take it.
Last note -- I see you are trying to replace all the components that are showing rust. In truth, I doubt that the rust on those component legs will actually work it's way into the component itself.