I feel like Ahri does pretty well against Fizz...
First, you've got a huge advantage in the early levels - abuse it. Auto him whenever you have the chance (i.e. don't need to do a last hit and he doesn't have a lot of minions to trade back for him). Q him frequently. Heck, Q him when he's on trickster so you get the MS to avoid his damage and then the return Q true damage still hits him.
NEVER use your charm before he uses trickster. If he doesn't use trickster, you just traded his low cooldown strong ability for your high cooldown hard-to-land ability for the entirety of laning phase - pretty good right?
If he ults, ult in retaliation, Your ult has a 10sec longer cooldown so be aware of that, but really it doesn't come to much. When your ult is almost up, just back up a little because his is up.
He can roam more safely than you, but I feel like Ahri is better at ganking a lane. Unless Fizz has his ult he really can't do anything on a roam aside from damage. A simple ping to back up should be enough. Place a control ward deep in bot-river, and when he roams bot you roam top. Don't follow because he'll 1v1 you, but go the other way and you'll probably be more successful than him. That, or just push tower mid. Either way, you'll eventually outscale him if he doesn't get kills. Fizz needs to get ahead or he loses really.