NewRelic's product screenshots look really nice, but 1) the hosted nature and 2) the price were turnoffs. We might revisit it at some point, though--there are a few features in there that would be awesome to have.
Their sales dudes like startups, we were only lightly funded when we started using them - garth@newrelic could probably help you.
(Btw not connected in any way, jsut a very happy user that convinced enough companies to try them, that I think you would be a good match, too)