How about just some company that issues banknotes backed by BTC?
Good idea, that would be a bank.
The first bank to begin dealing, trading and providing accounts in bitcoins will get some of my business. It is just a matter of time.
If that works then I'd imagine you see credit cards and everything else that goes with conventional banks.
You could also have quick payments based on trusting the bank etc.
Also I'd imagine that the odds of getting ripped off at say a restaurant are pretty low.
I'd let my customers start a transfer and walk out, if it proved to be a bad idea then I'd stop.
If you're not going to make them pay at the time they order though you're not really taking much more risk anyways.