I had the OP's problem, in that a 5 Gen 30 GB iPod was slowly dying, and I debated what I should replace it with. Eventually, I ended up with a refurb 80 GB iPod, am very happy with it, and readily recommend it. It has an excellent battery life and easily holds my pretty extensive music collection (and I don't have any videos, so don't need extra space) on it.
Cheers and good luck