Other than maintenance and opportunity costs for buildings, I wonder how else a size 20 city is better than two size 10's. The raw food required for a big city is way too big, I agree, but I'm not sure it should be linear.
Well the obvious answer is SPs. Having more cities increases the cost of the next SP by 30% (standard map) for each extra city. So an empire of 5 size 20 cities will have 100% + 4 x 30% = 220% of the base SP cost. Compare that with 10 size 10 cities and we get 370% of base SP costs. If the size 10 cities build monument and theatre and the size 20 build an opera house the two empires would make the same amount of culture per turn. The culture from the 5 cities is 68% more effective meaning new SPs will be gained faster and you should get more. This effect is compounded if fixed cultural sources are added such as CCS and puppets.
Are these extra SPs worth what you have to give up or the extra effort to grow big cities? Currently you have to get to Biology for Hospital to get to size 20 in any meaningful timeframe.
This leads me to another point. Is it really fair to compare 5 size 20 cities to 10 size 10 cities? I have never really had that much space available without conquering and razing. So maybe a more reasonable comparison would be 5 size 15 cities (founded and annexed) plus 5 puppets (size 5 to keep pop equal) versus 10 size 10 cities on the same map with capitals annexed and other conquered cities razed and settled. We have the same pop, same tiles and same timescales. It is much more practical to assume a few big cities associated with some puppets (growth suppressed by TPs). The puppets will help with research a bit, help a little bit with culture and cost nothing extra for SPs and probably break even in terms of gold. They will probably build some colosseums as well so happiness is probably pretty equal between the two empires.
It seems obvious to me that if that is a fair comparison of the options then even if the 10 size 10 cities are ahead on production, gold and even research, the 5 size 15 cities plus 5 puppets will be well ahead in SPs and that can affect the production, gold and research in other ways once the extra SPs come in. It depends on your strategy, for research, economy and SPs as to which is best.
The best way to get bigger cities in the game earlier is one of Ahriman's suggestions: make a building that lowers the food requirement. Right now, if I have a size 10 city and I want more population (because of excess happiness), there's no way in hell I'm waiting for my city to grow. I'm building a new city. You're absolutely right in that Maritimes are the biggest culprit of this by far.
The other problem is that more cities means more happiness, which increases the population threshold. I feel like there needs to be more aid for big cities in getting more happiness. I was thinking of high maintenance buildings that "gives happiness equal to x% of culture", or maybe even simply "gives happiness equal to x% of population". The former's harder to balance but encourages cooler specialization.
Agreed big and medium cities need a growth boost in the early game. A simple fix might be giving the granary 2 food and +25% and then reduce the Hospital to +25% when it becomes available. Small city ICS (as per Sulla) will not benefit from a granary like that but any city growing to size 10 and beyond will be significantly boosted.
Another good idea I've seen floated is to make the colosseum happiness dependent on city size, say 1 happiness per 3 pop. This severely hurts the current type of small city ICS, meaning they have to put a colosseum AND a theatre in each of their now size 6 cities. That's very expensive in hammers, rush gold and maintenance. But it helps the medium and big cities now, and encourages them to grow as each 3 pop only costs 2 happiness. A size 21 city with that colosseum plus a theatre and running 6 Freedom specialists will get 7 + 4 + 3 = 14 happiness covered (4 more than at present).
There are many ways the balance between small cities, medium cities and big cities can be tuned and altered. The worry I have is these solutions to the problems might hurt the AI and cause that to be even worse (I know that hardly seems likely

). We may have to accept a cheating AI that uses different rules for growth and happiness than the players have. I am prepared to accept that if we get a better balanced and more fun game.