This is a fascinating subject.
I think one question that has to be addressed is how you got your powers. Were you born with them? Have you studied under some spiritual guru? Have you discovered an ancient book of magick? Have you sold your soul to the devil? The answer needs to be consistent with your personality, and therefore the type of effect you'll perform, if it's going to be believeable. You don't necessarily need to explicitly state this back story as part of your presentation, but I think you need to know it, otherwise the presentation won't ring true.
Once you know what your "origin story" is, then you have to answer another question. Why are you performing at all? Especially table-hopping in a restaurant or on the street? If you had real powers, why haven't you used them to become a millionaire or, at the very least, got a high-class theatrical show where you could showcase these genuine abilities more effectively. There are answers to this question, but its probably better that you find them yourself.
When these two questions have been answered, you're on your way to creating a coherent character who may well have some sort of genuine ability. Then, you will naturally find a category of effects which appear to exemplify this ability. So, to give an example, here's a possible back story with the type of effects that might suit it:
Your grandmother was a witch. While she didn't initiate you into all the secrets of her craft, she gave you enough tantalising clues that, after years of trial and error, you found that it was possible to manipulate certain aspects of the world through a recognition of our unity with nature. You're still in the early stages of mastering these skills, though, so you've chosen this performing environment as a good way to allow you to practice without drawing undue attention to yourself. Effects that suit this back story could include vanishes, productions, transpositions and changes of natural objects (stones, sticks, leaves, etc.). Perhaps you have an affinity with certain metals, so you can bend coins by creating a connection with the copper in them and moving that independently from the other metals in the alloy. Possibly, a deck of tarot cards could be introduced, and some card effects could be performed that have a flavour of divination.
I hope that makes sense. I suppose my overall point is that it's not any specific effect that is going to create the impression of real magic, but your playing of a believable magician character.