Don't lock into a brand or size at this point. See as many models as you can. That's the most important piece of advice here. Supply and stock issues will make that a lot more challenging than in the past, but you're coming from a completely different bike. Geometry changed drastically several years ago. There's also no standard reference for "small", "medium", etc. sizes. Bikes used to marked by the seat tube length and the rest of the geometry was pretty similar. That went out the window some years ago. Definitely try as many bikes as you can from as many brands as you can. Look particularly at stack and reach numbers (basically the height to the steerer tube and horizontal distance from the bottom bracket to the steerer tube). Those are pretty good indicators of fit. You can start comparing other variables but stack and reach can vary significantly for different bikes marked the same "size." Once you get a fit in mind, compare different packages at similar price points. Prioritize hubs, fork and shock because those are among the most expensive components and the ones that will effect ride quality the most. You may find one particular model in a price point is giving you, for example, a higher quality fork than the others. Don't sweat things like derailleurs, brakes, tires and seat. Oddly those are the bits that are used to sell bikes but don't bite. Shimano or SRAM derailleur or brakes is spec'd is going to be fine until you ride more and get picky. They all work well. Shifters are more important than derailleurs in terms of shifting, but few new buyers look there. Tires are wear items and easy enough to swap out. Seats are highly personal, cheap relative to the other components, and you'll find one that you like (everyone's sit parts act a bit differently). On a fixed budget prioritize those parts that have the biggest impact on ride quality. Quality-wise it's hard to go wrong with a bike from a reputable bike shop, whether its Specialized or another brand. But, don't buy brand; buy fit. Also, don't rule out a hardtail. It'll be cheaper than full suspension, easier to set up correctly and have less service/maintenance issues. A good hardtail will also ride very nicely. Whatever you get, make sure the shop sets up the fork and shock (on a full suspension) for your weight. You'll wind up playing with it as you ride more and develop preferences, but a bad set up will greatly affect your ride.
Buying a used bike can be a very good purchase but it is also a very risky proposition. You need to have a good knowledge of bikes or go with someone who does. You also already need to know what fit you're looking for and what you're getting with a particular bike. Too many used bikes are bought with mechanical problems either because the owner doesn't know any better or doesn't care that he or she is off-loading a problem. Used bikes can also be very over-priced. The owner lovingly rode, spec'd and serviced that bike. That makes it hard to objectively price the bike. If you look at used bikes, do it in person and not just on-line, know what the actual value of the bike is, and either you need to be knowledgable or go with someone who is. Not someone who is generally mechanically good; someone who knows how to work on bikes more than changing flats or lubing a chain. Also keep in mind a used bike, even an awesome, perfect one, may have out-dated geometry or fit. For example, the two bikes you posted both look to have steep head angles and short reach compared to current models. Please bear in mind that's a quick eye test and dependent on how the pictures were taken. Also bear in mind that may be great for you or it may not. Only you can decide that and for that you need to try out different options. I'm just pointing out that a nicely spec'd full suspension bike from 2016 may or may not suit you well compared to the very same model from 2021 simply because the geometry has changed. You can't just look at the brand or model.
