When you remove the gravel, the beneficial bacteria needs another place to hang onto. Yes, it will find spots on rocks and ornaments and such, but the biggest colony will always be in the filter, if you don't have gravel. So, to give the bacteria extra material, I'd stuff the filter full with additional media - that helps big time.
Also, never remove all the gravel at once! Do it in smaller steps, that way the tank doesn't get a huge shock from suddenly missing a gazzillion beneficial bacteria. It gives the colony a chance to setup tent someplace else.
I got used to bare bottom tanks pretty quickly. It is a lot less cleaning involved, considering how long it takes to really thoroughly vacuum that gravel every time. If you hate the look of bare bottom, you can go with those smooth black river rocks, and put a single layer of them loosely on the bottom. The black coloration also "hides" any brown algae. Try white rocks, and you'll see the brown gunk on there pretty quickly, while with black - well, its much harder to tell.
I generally wouldn't recommend getting the algae under control with chemicals. I hate putting anything chemical into my tanks, no matter how "fish safe" they claim to be. I got a few otocynclus (I hope thats the right spelling... ahem...), those are basically mini algae eaters. Very timid, don't grow bigger than 1 1/2 inches, and leave the goldfish alone. I hardly see mine, they are always hanging out on pipes or rocks.