From experience, the games from Gameloft aren't on the market. You have to buy them directly from their website. These games include N.O.V.A. HD, UNO HD, Avatar HD, etc etc. There are around 10 or so "HD" games that all have pretty good graphics. I'm not too sure how they are gameplay-wise but I've heard a lot about N.O.V.A... Check out videos on Youtube for this and other Gameloft games.
If you aren't from one of the countries that the full Android market is available in, then you won't be seeing ALOT and you won't be seeing the paid games if that's what you've been searching for. There's a sim emulator app floating around somewhere that would bypass that and as long as you have a valid credit card then you'd be able to buy games and stuff from the market and from gameloft.
Dunno about any really great free games that aren't on the market though..
Hope that helped!