I'm in the market for a new mobile phone.   

The one I have at the moment is rather simple, and I'm looking forward to getting a smartphone.  The iPhone does look cool, but it won't cut it for me as it's not going to work with my ubuntu machines - and as that's my operating system of choice, I don't want to have to boot into MS for anything... VM is a no-no too.  I'm pure ubuntu.
I fancy something that can hold music, works with Spotify (I have premium, so that offline stuff looks awesome), and has the potential of replacable SD memory, 16GB or greater.
So my choices.. well I could go with Symbian or Android on the phone - Windows Mobile is once again something that I don't want to spend time with.
Coming out on the 29th March in the UK (on o2, my preferred carrier) is the Sony Xperia X10 - and it seems to tick many of the boxes, aside from the fact that it's not yet available.  I'm also told it'll ship with Android version 1.6, rather than 2.0.
So, can someone please give me some advice on which phone works well with Ubuntu, what I should be looking out for, and which ones are best to avoid.