So far, the best deal I've found (and I'll probably be going with this one) is with o2-UK (owned by Telefonica):
On & On tariff. £31.00 Monthly Cost. Up-front payment of £249.99. 24 Months contract length. Unlimited call minutes. Unlimited texts. 2GB Data. 1 month early upgrade. Add £10 a month for insurance.
Feel free to add other information on other great deals if you know of any.