With the latest slew of Android handsets, there is a fair deal of flexibility for choosing operators. With that aside though, there are still limitations (unless you buy an unlocked handset). See below for a grid breaking down exactly which UK operator offers what (notice that O2 has none yet):

T-Mobile	Vodafone	Orange	O2
T-Mobile G1	HTC Magic	HTC Hero	Samsung Galaxy
T-Mobile G2 (HTC Hero)	HTC Hero	Motorola DEXT (CLIQ)
T-Mobile Pulse	HTC Tattoo	HTC Tattoo Ink

Popularity: 4% [?]