I would stay away from Sagem, Spice main reason being they'r not so popular and dont have good customer support. (Spice cell connection support totally suks)
What I'd suggest is check if the Nokia Ngage QD is still floating around. You should be able to still find one at around 5k. You can't possibly get anything better now for that money. No FM though, but it's worth every penny it costs, trust me.
)