story identification - Series of novels with immortal man and tribes with horses / telepathic cats in post-apocalyptic US

My memory of this is sketchy and I hope I don't jumble it too much. I read two or three books (possibly more exist) in a series in the late 1990s. The whole thing was mainly SF with a dose of fantasy.

The main character is a man who is immortal. He doesn't age and can recover from even the most horrific wounds. I'm not sure if there where other immortals (I seem to recall a woman and another man). As far as I can recall, immortals were infertile and couldn't have children.

He lives among a tribe of nomadic people who roam the prairies of post-apocalyptic North America on horseback (society like Native American prairie tribes). Among their tribes (there is more than one) also live huge (lion-sized?) cats who are telepathic and have near-human level intelligence. The immortal man is a leader among the nomads and, I seem to recall, he is instrumental in getting the tribes together in a larger alliance and gradually moving them East to the coast.

On the east coast, some cities remain (Pittsburgh I clearly recall) who have a medieval feudal society with a militia and knight-based military. (I clearly remember that military ranks among them had Greek-derived names, which was quite strange.)

There was also a small group of people who had retained pre-apocalypse technology (radios, trucks, helicopters, firearms), possibly survivors or descendants of the military or of some scientists. These people were antagonistic to the immortal and try to kill or capture him. The immortal had some narrow escapes. They mainly work in secret and avoid letting their presence be known among the tribes.

Answer

Kind of sounds like the Horseclans series by Robert Adams. (1975-)

Horseclans is a science fiction series by Robert Adams, set in a North America that had been thrown back to a medieval level by a full-scale nuclear war.

The books mainly concern the doings of the "Horseclans", a nomadic people originating from the "Sea of Grass"—the Great Plains from present-day southern Canada to central Texas, and from the Mississippi River to the Rocky Mountains, post-apocalyptically. The Horseclansmen were portrayed as fierce, noble and often gifted with telepathy, which came in handy for their dealings with their horses and "cats"—sabertoothed tigers that had been revived by scientific means in the years before the nuclear war.

Some people, including the Horseclans' founder and mentor-figure, Milo Morai, were "Undying"—effectively immortal or at least unaging and almost impossible to kill by means other than suffocation, drowning and decapitation. The Undying were also sterile, which was a source of anguish for some of them.

References:

https://en.wikipedia.org/wiki/Robert_Adams_(science_fiction_writer)
https://en.wikipedia.org/wiki/Horseclans