So after all this.... I decided to buy a Cowon. Since I had to buy two units (one for the wifey too) this was adding up to an expensive purchase. I bought 2 Cowon 4GB from Amazon for $134.95 each (free shipping in US) I also bought 2 4GB Kingston SDHC mems, and 2 pairs of Ultimate Ears Super.fi 3 from Costco on sale @ $49.00 a pair. All in all I spent around $500.00 for all of it... not bad.
Thanks for the recommendations, I am happy with my purchase... I think that by the time I am ready to buy another one, bluetooth and wifi will be a standard feature for mp3 players.