Yep, the Apple Store's refurb. section is a good place to look, as is
www.smalldog.com as they sell great refurbs w/ great service.
But honestly man, I've been using eBay for 3 years and though security may be nerve-racking, you should honestly not scratch eBay out. Just be smart, buy from reliable sellers, email questions and see how fast and if at all they respond, just to see how earnest they really are, and you'll be fine. eBay has literally saved me thousands in the past 3 years, and I'd highly recommend looking there for iPods as well. But if you're determined not to use eBay, definitely use
www.smalldog.com Good luck!
EDIT: Got the direct link to SmallDog's refurb iPod selection for you:
Just Click Here