If you go with a 3 payg sim, you can generally get it unlocked in around 24 hours (they quote longer, but it hasn't taken any longer than a day for anyone on here). You go onto their website at
www.three.co.uk/unlock and fill in the form. They'll call you back (if you miss it, just dial 333 and go for the 'any other technical problems' bit and say you missed a call about unlocking) to take a payment of £15.32 and it should be unlocked shortly after that.
You can use a giffgaff sim in an o2 phone, but it looks like tesco mobile works differently.