Use common sense when deciding how many calls to make. For example, if you're making a web application, try not to hit the API on page load.
How do I balance these two things and get an application to be popular?
I keep a personal count of how many API hits I make on my "big" application (as a by-product of the mashery days), and the number of queries per day goes up and down by a couple orders of magnitude. What's reasonable? Where are we most likely to hit a rate limit?
We are in the process of rewriting the terms-of-service. We realize that there are a number terms in the TOS that were rather unfriendly for developer. I believe intent of the no-caching policy was to prevent nefarious 3rd parties from crawling our site and repackaging our data in their own service. There are other ways to ensure this doesn't happen - so the next version of the TOS will not have this caching restriction. (As an aside, I believe the Last.fm TOS has a provision that requires you to cache their data for at least a week.) I suspect that nearly every one of our 3rd party showcase apps violates to some extent this no-caching policy.
As for rate limits - there is an enforced rate limit of 120 API calls per minute per applicaition key. Beyond that rate and you'll receive 'rate limit exceeded' errors on the call. That seems to be a reasonable rate limit for many apps (especially if you are caching data). We have the ability to modify the rate limits on a per APP KEY basis. So if you have an application where you suspect that you might need to exceed these limits, we can perhaps adjust your rate limits. Send me an email (Paul@echonest.com) if you think this is the case.