How big you need depends on how much used space you have on your g4's drive, and how far back you want to be able to go.
Considering the comparatively low cost of space until you get to the latest cutting edges, 1TB drives are very economical right now. You WILL pay more for a firewire drive than a USB only, but be warned that powerpc accesses USB even slower than intel, so your backups may go slow.
That being said, once the initial backup has run, the incrementals don't really need much speed, so you may not get that much value from paying more for firewire. I'd still get a firewire though, as you will probably be using the drive for other things where you DO benefit from the speed boost. Unless it's a newer pbg4 you won't have fw800 though.
I've had good luck with OWC kit recently, I'd suggest something like
this drive. It's 1TB, it's small, and they appear to be reliable. It does NOT come with a fw80o to 400 (9 pin to 6 pin) cable, so get one of those too. Get it from them, the retail stores gouge badly on cables. I don't recommend an adapter unless you specifically think it will be additionally useful at other times.
My other retail recommendation would be a lacie rugged in
500 GB or
1 TB size. I personally use the 500 as my portable service drive, appreciate the rubber bumper, and it's a good performer. They have one 400, one 800, and a usb mini port on them so cables are not usually an issue. they also come with cables. I didn't used to like lacie brand at all but now that they've stopped making crappy 5.25" ext that cook their hard drives, I'm gaining respect for the brand.