Second-hand.
My $800 (adult) bike, a "hybrid" (a Kona "Dr. Dew") is 7 years old. I think I saw its current value (now being old) estimated at $230, though I don't remember where. I'd rather have it than a new cheap bike -- nice gear-change, great brakes, solid easy-turning wheels (and great tires).
They say, I don't know, that better components need less maintenance.
On this I change the chain (and sometimes the cassette) and brake pads twice a year or so (e.g. every 5000 km); and changed the bottom bracket once after about 25,000 km when the pedals started to wobble slightly; and change the tires once every 5 years or so; and lube the chain, and that's all the maintenance it requires.
I get the impression that there are, approximately, three kinds of bike:
- $150 from the department store
- $550+ from the bike store
- $1500..15000 racing bikes
I'm thinking a second-hand version of category #2 could be better than a new #1.
Replacing all the replaceables though -- new tires, new brake pads, new chain and cassette -- might cost a good fraction of $100 (so if that's an issue then find a bike where these aren't worn, so that you'll have miles to go before they need replacing). These components do wear, if the bike is ridden and/or as the years pass, I'd expect that and not see it as a fault of the bike (though that could be something that needs service to make a bike ride-able).
Edit to add: if you're "on gravel roads and maybe light gravel trails" then you might want good tires, puncture-resistant tires, maybe touring (long distance) tires.
The tread doesn't matter (and a thick/heavy tread i.e. knobbly tires just makes it slower, because your pedalling effort goes towards deforming the knobs on the tires as it rolls, maybe this kind of 'mountain bike' tire is for mud or something I don't know), what matters to me is the resistance to little chips of stone.
I ride a gravel cycle path all the time and the tires are among the best components on my bike -- I bought them specially, they didn't come with the bike. Someone with a road bike and lighter tires maybe wouldn't ride that path.
A wider wheel (mine, being made as a 'hybrid' bike, are like 32 in width rather than the 23 you'd find on a racing bike), might be more suitable too for that -- apart from or as well as puncture-resistance, the width of a tire is related to its pressure (because "tire pressure" multiplied by "surface area of the tire's contact area with the ground" equals "weight of the bike and rider"), so mine are pressurised to like 80 instead of maybe 120 that you'd find on racing tires (which contributes to their ride's being described as "teeth-rattling" in a comment below). I think (i.e. it feels as if, perhaps I'm wrong) the relatively-heavy tires contribute to the bike's "suspension" -- cycling gloves with slightly padded palms (between the heels of the hands and the handle-bars) help with that too.