I made few speedtest.net measurements with my Jolla in 3,5G network and got 18 Mbit download speed when the signal was strong. So it is good even with 3,5 G. However, yes, in some crowded places 4G would be even better.

Not neccesarily - often sims are delivered as a sort of "russian doll" - you get the ancient "credit card" with a mini-sim you can break out, with a micro-sim inside that you can snap out again.

I'm using a (formerly) micro sim in my n900, it just snapped back in to the plastic ring left when I broke it out of the mini-sim to use it in my N9 for a while.

(hope this incoherent ramble is understandable)

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/