You'll need to use a single platter drive (despite the size :) ) which are denoted by Toshiba by the GAL or MAL suffix. I just dropped a 20GB drive (either MK2004GAL or MK2006GAL) in mine and it works like a charm. To my knowledge the largest drive easily available (ie eBay) is the 40GB MK4007GAL. You can also get a 30GB one - MK3006GAL.
Well worth it - the first gen is my favorite, although closely followed by the third gen (the original iPod touch!), and it's great to be able to continue to use it with a reasonable hard drive size.