My first ever public performance was at a park for kids. Then I was a regular at a food pantry and I would perform coin and card tricks for kids. After about a year I started volunteering at a special needs camp for kids and they gave me a parlour-esque type of show for the last two summers.
For stage, I just happened to be at the right place at the right time (magic convention
) when Ayala asked me to assist him on his closing act. I just recently got the greenlight to head my own solo stage act. How that happened was I was doing a theatrical play and I was talking to the owner of the venue and he agreed to give me an hour to hour and a half show at some point in May.
So my advice is best summed up by a Woody Allen quote: "80% of success is just showing up." So really you just have to make things happen. I know that is a very broad statement but just keep putting yourself out there and get active in networking and eventually you will talk to the right people.