I am pretty sure that as long as you have the latest firmware you can use the larger cards. I just recently sold my 20D and am now using 8GB cards in my 1DMKII with the latest firmware and I am thinking they are really close in age.
This probably just made things even more foggy for you. Clear as mud?
I just recently bought three 8 GB Sandisk Extreme III cards that I'm using in my 20D. they work just fine. well, at least now that I got a replacement for the one defective one I had.
As far as prices go, I bought mine from Adorama while Sandisk had a rebate offer, and used Bing Cashback. Got all three for $75 total after getting my rebate and cash back. Not sure about current prices though...
I am using 8 Gig cards in my 20D with no problems. My wife brought me a 16 Gig card instead of 2 8Gig cards one day and it will only format in the Camera as an 8Gig card. I haven't tried to recover it back to 16Gig as yet (if it works don't mess with it). They might be overkill but I am using Extreme III Sandisk cards as I've never had one go bad on me yet, fingers crossed.