Your frame should take about 2 hours to sandblast. We are usually right around $150 to sandblast a small frame, 250-300 to clean/phosphate wash and powder coat. Do some searching for better$$. Make sure you do an aggressive media like sand, aluminum oxide, black beauty (coal slag). Not soda- works great on paint but softer than rust. Consider an etching type sealer on the bare frame too as it will have phosphoric acid, just like those rust converters. The acid strips a small amount of iron off of the surface, instantly becomes iron phosphate, and bonds right back to the steel. Kind of a cold plating process. Epoxy primer is a good next step. All this assuming you aren't powder coating it.
Also, look for a semi gloss black for a finish vs. gloss, it looks way better over imperfections. Spraying is king over brushing for looks too.
Good luck!