My story if it helps.

I had 0 credit 3.5 years ago. I signed up for a secured credit card where I banked and used that for about a year, I upped the limit, then went unsecured and upped the limit some more. After about 9 months I was able to get a rewards card (not a signature with a lot of bonus miles but a platinum with a 2500 limit) with BOA. After 6 months with that I was able to up the limit to 5000 which is what most of the Chase and BOA minimum limits seem to be on the nicer bonus cards. I called for the signature, moved most of my credit line from the old card to the new one.

I could have probably shaved some time off if I pressed things, but from my experience it took about 15 months to go from no credit to signature card. I just now felt comfortable starting my first churn, never had a chase card before and was approved for 3 and the SPG amex.

I agree with Altoid start small, a chase freedom is a good choice, doesn't need 5k in credit and has no annual fee.

I'd find a similar card with BOA with no fee and low limits and ditto with a Citi one for farther down the road. The reason being I've been told banks like to know that you're a good credit risk from past experiences (and not just a credit report), since all my accounts were BOA I had to talk a lot to get all 3 Chase cards approved due to my lack of history (3.5 years) and never having banked with them before.

Anyway I'm a newbie myself, hope my experience helped.

edit: I also meant to say what will restrict you the most is lack of credit history, it was the largest hurdle I had to jump through.