I generated a pair of keys i.e. private and public keys using Putty's key generation tool. The public key was provided to the third party we plan on connecting to so that we only need our private key as a form of authentication when connecting. However when I connect to the server, the finger print I get is different to what was generated in Putty. Is this normal? Should I expect the fingerprints to match? Why would it not match?
Yes, it is normal.
In SSH, servers usually have their own keys, often called "host keys", used by PuTTY to make sure it is connecting to the right server; a SSH client will verify the server's key as the first thing done after connection. When PuTTY displays the key confirmation screen, it will show fingerprints of the server key, and your user key is not used for anything yet.