Yes, payment is required. Someone early on posted an article that said downloads would cost $5 for NES games; $10 for SNES games; and $15 for N64 games... though I think the final costs will actually be less. GC games will require the disc itself.
In answer to your other questions, rumor has it that Nintendo's hard drive (seperate) will be channelled through a usb port. This may be too good to be true, but if it is, then you can pick up a regular external hd for $70 and have 120 gigs of storage on there. With regards to memory cards, GC games will still use your old GC memory cards... so they can just be plugged in to your Wii.
