Vodafone provided me with a sim without the 'Russian doll' adapter, but T-mobile pay as you go sims can be bought for 99p in shops and come with them.

As for Vodafone tariffs, I joined on a sim-only deal through quidco at a time when they were offering £130 cashback. Currently they've cut that to £80, but if you keep your eye on it, they might push that up again:
http://www.quidco.com/vodafone/