A "costume" looks like a cheap costume because it is made with cheap, unsuitable materials using quick assembly techniques with minimal finishing; if you want it to look "legit," you have to approach it as actual apparel, not as a "costume," and you'll have to spend some money on the materials, as well as time on the construction. "Cheap" fabrics will not get you the look you want.
Similarly, many "costume" patterns are geared toward this "cheap" approach; you'll likely need to make modifications or enhancements to whatever pattern you may choose, or to find a higher-end pattern (which will be more expensive).
There's a reason "cosplay" is considered an expensive hobby; even a simple garment can take many hours and a great deal of expense. (As a personal example, the belt for one of my own costumes cost $80 in raw materials.)
For a steampunk-style costume, consideration should be made toward the time period being evoked by the style; avoid lightweight and synthetic fabrics. You'll want 100% cottons (denims and other bottomweights for outer garments), wools, linens (good for shirts), and leather/suede. Note that synthetic suedes are fine if you like that look and want to avoid the cost or morality of real suede; synthetic leather is not a good substitute for real leather in belts and similar garments. A decent quality cotton twill can start at around $10/yd, linen often runs $12-20/yd, leather is generally priced by the size of the piece (or hide) and takes considerable extra effort to work with.
Some stores will offer sales or coupons; this will be your best bet to save money on your materials (and be sure to get a feel for the average sale vs the average coupon; at my local shop, linen never goes on sale for a better price than I can get with a coupon, but flannel almost always goes cheaper than the coupon price). Sign up for any emails, mailers, or apps your local stores have and comparison shop so you can save some money and use the savings to help yourself get higher quality materials.
Ultimately, what you get out of the project will be determined by what you put into it. If you use cheap materials and cheap construction techniques, your end result will look cheap. The only way to get the "feeling that it is legit" is to make it legit.