(Post was slightly updated earlier with a few rewrites and a higher quality replacement image, specifically one of the terminal’s design, in the “Several shots of the various facilities of the airport” section)
The following is a few tabs of possible airlines, both regular and historical, alongside special/historical liveries that could be added with the theoretical addition of ABQ - be it as a part of the airport’s progression pass, or as a general, standard addition to enhance gameplay.
(Do note that some airlines listed may involve aircraft types not in-game as of yet.)
(Lots of sources for airlines came from the Cavalcade of Wings website, which provided a ton of useful info; go check them out if you’re interested to read more)
Regular Airlines (2010 and later)
(This refers to airlines that either are still active, or are defunct, but existed either until/past 2010.)
1: Advanced Air
I mentioned them already in the post above, but I figured I’d bring them up again since we’re on the topic of potential airlines. If you’re unfamiliar, they’re a smaller airline operating quite a wide variety of aircraft across the US, though from what I could gather, they only run King Air 350s out of ABQ, such as the one pictured above.
2: Ameriflight
Also mentioned in the above post, I found some new context about this airline: Ameriflight used to have quite a network in ABQ, I believe at one point having a base around the mid-2010s, but in the present I’m not so sure.
Using aircraft such as the Piper Chieftain above, they served smaller cities across the state - though by 2019 services were beginning to wind down with the retirement of the type, and nowadays ABQ is no longer displayed as a base on their website - though it seems to still be served to this day.
3: Boutique Air
This airline actually has quite a storied, interesting history with ABQ, beginning in January 2015 under an Essential Air Service contract (though its services with New Mexico began in July 2014) serving various smaller airports in New Mexico, and even a route into Colorado.
However, in 2019, the airline began to face its first bit of trouble, as EAS contracts/routes were awarded to other airlines, such as Advanced Air mentioned above, and in 2021 the airline began to endure operational issues, leading to cancellations of various EAS contracts across the state.
The last remaining route, ABQ to Carlsbad (CNM), was however renewed by the airline and was kept afloat for a few years, though in November 2023 this contract was also given to Advanced Air - this led to the ceasing of Boutique’s operations in New Mexico as a whole, including ABQ.
4: New Mexico Airlines (2007 - 2015)
The first and only defunct airline in this tab, this airline actually didn’t originate from New Mexico - rather, the brand actually originated from the airline Pacific Wings (formerly Air Nevada), which was originally based out of Las Vegas before switching to Hawaiian service.
Similarly to the above case of Boutique Air, this brand of Pacific Wings was created to serve smaller airports in New Mexico under EAS contracts as well, with services beginning in July 2007. From there, the airline had a standard history with no serious issues - up until December 2014, when the FAA issued a grounding for the airline upon finding serious maintenance issues in the airline’s fleet. Despite the airline restarting (and cancelling) services briefly twice throughout 2015, New Mexico Airlines was quietly shut down by May of that year.
Historical Airlines (2009 and earlier)
(This refers to airlines that ceased operations prior to 2010.)
1: Great Plains Airlines (2001 - 2004)
A small, short-lived regional airline based out of Oklahoma, yet one I still found notable, nonetheless. They not only operated services to the airport with the Dornier 328 (both variants) such as the one pictured above, but also later worked with another airline, Rio Grande Air, to provide a feeder network to some of the smaller airports of New Mexico from ABQ. Despite this, the airline struggled to find a suitable market and shut down in 2004.
2: Rio Grande Air (1998 - 2004)
Commencing operations in 1998 as Edelweiss Air (yes that was its name), this airline originally was dedicated to serving as an air freight carrier at first - service was originally aimed for May 1995, but it was delayed for a few years. In March 1999, the airline began commuter passenger flights between ABQ and Taos (TSM) in New Mexico using Cessna 207s - though by the end of that month, the airline introduced the Cessna 208 pictured above, and as mentioned, later began working with Great Plains Airlines to provide a feeder network to New Mexico. Despite ambitions for growth, such as plans to acquire the Beechcraft 1300, the airline shut down operations in June 2004.
3: Western Airlines (1925 - 1987)
Western had an extensive history with not just ABQ but Albuquerque as a whole, being one of the first airlines to serve the area around 1929, before ABQ even came to be - though the area was more so a stopover for the airline. This would continue off and on for the airline until about 1933; after which the airline attempted to return and establish routes to the area, both in 1945 and 1958, yet these were not approved.
Western would not be granted a return to Albuquerque for decades until the Deregulation Act of 1978; services were finally restarted in October 1981 - at which point it had been nearly 50 years since the original service to the airport. Nonetheless the airline went to work at ABQ, with 727s being regular sights, and those were later backed up by 737-200 and 737-300 service. Western later merged into Delta in 1987, not many years after returning to Albuquerque - however I do think it had a notable history with the area, nonetheless.
Special/Historical Liveries
(This refers to special liveries, historical liveries or both that could appear at/with the airport.)
1: American Airlines (B738): TWA Heritage Livery
Now, this livery is already in-game, I’m aware, though you might be wondering about the context.
TWA was one of the biggest airlines of ABQ’s history, being possibly the first airline to introduce the Jet Age to the airport in 1961, with the Boeing 707 and Convair 880, as well as the first widebody airliners, specifically the likes of the L-1011 and 767 - and even tried their hand at establishing a mini-hub at the airport, though this proved unsuccessful in the long run.
With the end of the airline in 2001, TWA had served the Albuquerque area for over 72 years - they played a huge part in making the airport into what it is today, and as such, that is why I feel the livery could fit well at this airport.
2: Southwest Airlines (B732): Desert Gold livery
There’s quite a bit of media of these aircraft running around ABQ - and given that they’re unlikely to be available in-game through regular map contracts, it would be great to see them at this airport as a nice representation for the history of Southwest and this airport.
(You could also make the same case for the B733 if it’s not added as a map contract aircraft.)
3: Southwest Airlines (B737): New Mexico One livery / Southwest Airlines (B738): New Mexico One livery
It’s probably a bit of an obvious choice, I know… 
I included both the versions of the livery because they’re… essentially just the same livery.
Unfortunately, I couldn’t find any media of the 737-700 variant at ABQ (whereas the 737-800 shot on the bottom was taken there). So, I’d personally prefer to see the current New Mexico One… but of course, either version works at the end of the day.
4: United Airlines (B739): Continental Retro livery
(This picture, which was used in the suggestion linked above, is actually the only shot of the aircraft at ABQ I could find.)
You’re probably also wondering what this context was for this livery, so here:
Continental was another major player at ABQ, with a significant presence in the southern United States from the day it was founded in 1934; its original route involved a route originating from El Paso, its hub, and made a stop at Albuquerque (ABQ was yet to be founded at the time) along the way to Pueblo in Colorado.
The airline also was one of the first operators of jets to ABQ, bringing the Boeing 720B in 1962, and would later establish a small hub of shorts, thanks to the help of various feeder airlines operating under the Continental Express brand.
At the end of Continental’s life, they had been remarkably serving Albuquerque for 78 years, making them the airline with the current longest history with the area, even surpassing TWA’s record, and thus establishing Continental as another impactful and significant airline in the context of ABQ’s history.
5: Trans World Airlines (B762): 1979 - 1995 livery
As you might recall from the context provided above, TWA operated both the L-1011 and 767 (-200, unsure of -300) to ABQ, with the 767s such as the one pictured above filling in for the L-1011s on occasion. There is little media of such operations, but I have seen some discussion on forums about it such as here on Airliners.net and here on Facebook (where I got the photo from) to confirm that it was indeed true. As such, it’d be another great addition with the airport if it’s ever added, serving as a nice bit of a callback.