Three approaches I use are:
- Request an odd amount from the ATM to force it to dispense both smaller and larger bills. For example, in HK I might withdraw 800 HKD to get 1x500, 1x200, and 1x100 notes.
- Change larger bills at the hotel. They deal in large amounts anyway, and they're more understanding of a foreigner's needs. Also, they have your credit card information (and often passport number, too) so they trust you more than a small-time shopkeeper would.
- When you know you'll be visiting the same country again, keep small change (e.g., enough for a simple meal or a short taxi ride) for your next trip.