It is the to get a PAC number before you get a new phone so you can tell it to Vodafone when you are getting a contract. It is also possible to get a contract from Vodafone first and then get a PAC number and give it to Vodafone afterwards.
From what I can remember, in only takes a few hours from calling Vodafone and asking them for PAC number (never done it with O2) until they send it to you in email. What is important though, PAC number is valid only for 7 days before it expires. If you don't use it in a week you will need to get a new one.
I guess what you should do depends on one thing:
a) if you expect to walk into the vodafone shop and come out with the phone, get the PAC before going to vodafone
b) if you you think they won't have the phone for there and then for you to take home, get your contract from vodafone, wait for you phone and then call O2 for PAC. When you get your PAC call Vodafone and give them to port you number.