Venkat,

I believe First USA has an offer with its BA Visa: 5000 BA miles and no fee for the first year. Their customer service number is 1-800-577-0633.
In addition to that there is of course the Starwood Optima. I haven't applied for one yet, but I believe they offer 1000 Starwood points upon sign up, no annual fee, and the rate of exchange is 1=1 (or 1=1.25 if you accumulate at least 20000 points). The advantage of the Starwood Optima is that you can transfer your points to a number of airlines. On the down side, though, it's an Amex, so it's not as widely accepted as VISA.

Hope this was helpful

Honu