zuki-
last 2 years, when I played in a duo, most of our earliest gigs were done at private clubs,lodges i.e. Amvets, Eagles, Moose Lodge, etc. . . many of them are always looking for some new entertainment to try. We got many other jobs booked from playing just a few times at the Eagles club - we even landed a private wedding!
I'm just starting again, this time a solo career, and I'm going to start the same way - the smaller private lodges, our new coffee house that just opened, etc - make sure you have some biz cards with you!

Best of luck to you - let me know how it goes!

Jill