We have a babysitting coop that we are part of. Its a sort of community where all the families know each other, have kids the same age, and the kids are comfortable playing together. The babysitting each others kids part is almost secondary to the community that it creates.
The babysitting coop was created by someone who put up a flyer at a birthing class, but we have since added new members who are friends with current members, or meet at library story time, or something like that. We use sittingaround.com for our points trading.
Is there one in your area?
Also, coop preschools where the parents work a day a week and the kid goes a few days a week could be an option. They're not usually free, but cheaper than traditional preschool.
Also, I second the poster to go to places at the same time every week. We are regulars at a story time, and a certain park. Your kid will make friends.