When it comes to coverage, remember that despite the dozens of companies offering contracts, the number of actual, physical cellular networks is quite limited. When you sign up with Tesco, Virgin, et al, they issue the SIM cards, do the billing, and so on. The actual operational side is merely sub-contracted out to one of the other networks, so if both Acme Cellular and Fly-By-Nite Telecoms use the same physical network, coverage will be identical.
The four main GSM networks are:
Vodafone (GSM 900 & 1800)
O2 (originally known as BT Cellnet, GSM 900 & 1800)
T-Mobile UK (originally Mercury's One-2-One, GSM 1800)
Orange (GSM 1800)
There are two very new start-ups on the scene now providing just GSM1800 service as well -- Opal Telecom and TeleWare -- so expect to see more usage of these over the next few years.
All four of the main GSM companies plus the relative newcomer Hutchison 3G Ltd. provide 3G 2100 services.