The 5V GPIO pins are connected to the 5V rail, so a fan that doesn't need a ton of power will be fine. However, that 3 wire connector is odd. It looks like it has 2 grounds and a single 5V, while the Pi has two 5V pins and a single ground. You should replace that connector with one that fits better, and only uses one ground and 5V wire (don't connect the other wire).
On the other hand, fans are noisy and blow dust all over your Pi, so I don't like them. Get a Flirc case and you won't need a fan. The top and sides of the Flirc case is a one piece casting of aluminum that contacts the SoC (CPU+GPU), so the case itself acts as a huge heatsink. It will keep your Pi3 cool without the need for a noisy, dusty fan.
And it looks good too!
Click picture for Amazon USA link.
There is a newer Gen2 version that is specifically made for the Pi3, and an older version for the B+/Pi2, but you can use the B+/Pi2 in the Gen2 case as well, you just won't be able to see the LEDs. I don't recommend a Pi3 in the older case because the SD card is hard to access.
If you hear the fan speed changing during boot, then your power supply is probably inadequate. Some phone charger type power supplies have very poor voltage regulation and will drop well below 5V under relatively light loads. They will still work fine for charging a phone, because battery charging does not require very precise voltage control (4.5V will charge your phone, but it won't run your Pi3).
It could also be the micro-USB cable you are using to connect the power to the Pi3. Many of those have thin wires with too much resistance to deliver the kind of current a Pi3 might need.
The official Raspberry Pi Foundation Pi3 power supply is rated for 5.1V at up to 2.5A and has nice fat 18 gauge power wires.
My mind is like a browser. 27 tabs are open, 9 aren't responding,
lots of pop-ups...and where is that annoying music coming from?