Has it ever happened before that a major party in the USA has increased its number of seats and still went on to lose the presidency, or has losing the presidency always come with fewer House/Senate seats for your party?
Yes, as recently as 2016. The Democratic candidate, Hillary Clinton, lost the presidential election to the Republican Donald Trump, despite her party picking up six seats in the House of Representatives, and two seats in the Senate.
Before this, the next occurrence came in 2000, when George W. Bush won the presidency for the Republicans, with the Democratic party gaining four Senate seats and one House seat.
In 1996 there was a mixed result, with Democrats winning the presidency and gaining a couple of House seats, but also losing a couple of Senate seats. In 1992, the Democrats were also successful in the presidential election, despite losing nine seats in the House. The Senate retained its pre-election composition.
1988 saw another complete example - Reagan (R) won the presidency while the Democratic party increased their hold on both the House and the Senate.