Would be helpful in responding if you could post; the actual trouble codes the dealership retrieved, also whether you have experienced DPFE exhaust pressure hoses coming off.
Emissions warranty, which covers cats, is 8yrs/80,000 miles.
There was also a recall on these for '95/'96 cars, so dealer should have checked if recall had been done or was still applicable.
The pre-cats are in each of the exhaust manifolds and then there is the main cat under car. Replacement of all of them would be in the $2,000+ range you quote.
Alternate solution wouild be to gut the pre-cats and replace only main cat but you would first have to research how that would affect passing your State's emissions tests.