The largest footprint for an app I have ever seen was 8-10mb, and this was on Windows Mobile. The iPhone certainly has more storage space, but I don't think that means it will automatically cause the install size to skyrocket.
I think it will vary from less than 1 megabyte to 50 or so megabytes for your more normal applications. Medical reference apps, and games may weigh in with several hundred megabytes, but I still don't see them cresting 500.
I could be wrong, but I just don't see it happening.