As everyone has said, the most important thing about painting metal is that it has to be CLEAN ! Spotlessly clean !!
A couple of coats of rattle can Rustoleum (read directions for temps, time between coats and final cure time) is all you need for something like a vice.
If you want a very "durable" paint and do not want epoxy, use an alkyd enamel with a hardener (catalyst). The hardener is optional but it does make a difference on durability. One excellent alkyd enamel specific for metal that see a lot of weather, is Valspar® Tractor & Implement
Enamel Paint. Limited color choices, but it is what they use on farm and construction equipment.
If you are spray painting sheet metal, take a tip from the body guys. Spray on a coat of "high build" prime and let it cure. Then spray a very light "guide" coat of a contrasting paint. Using a hand sanding block or a "long board" with fine grit paper, start to sand off the guide coat. That is when you will see minor scratches and low spots. Clean, repeat the high build primer, guide coat and sanding, but go to a finer grit. Keep repeating until you are happy, then apply the top coat.