They had three quite distinct phases:
Peter Gabriel / Steve Hackett years - Theatrical, long, complex, and sometimes drawn out songs and albums which are amazing to truly sit and become completely absorbed in, but they take effort. The music in the concert clip above was from that era, specifically the "Lamb Lays down on Broadway" double LP. It is very good, but "Selling England by the Pound" is my favorite of that era as they had to add some wasteful filler to "Lamb" which make it hard to sit through from beginning to end. Every album up to "Lamb" is from the Gabriel/Hackett era and all are pretty good.
Post Gabriel Prog Era - This was the era immediately after Peter Gabriel left and their musical sensibilities were still focused on longer, more robust songs, but they started being individual songs so an album wasn't so much a long opera but a collection of related songs. The best is the first one, "Trick of the Tail", when Steve Hackett was still with them and contributing. The other two, "Wind and Wuthering" and "...and then there were three", are also very good if you like traditional prog rock.
Top-40 Era - With the release of "Duke" and "Abacab", Genesis started experiencing top-50 commercial success and many of the songs, while still very well written and still showing their talents as musicians, were more pop sounding and easy to listen to even if you didn't care about prog rock or complex musical arrangements. If you like that sort of thing, I think the album, "Genesis", is the best bet, but "Duke" is a good one as well.
If I had to choose one album, and since I love prog-rock, I would choose "Trick of the Tail."