Definitely something not right with that motor.
Cat removed won't do that much to the idle, the 02 sensor is before the cat, so the car really could care less... I would consider pulling all the injectors and sending them to
WitchHunter Performance - Injector Cleaning & Flow Testing Services, they smoothed out the idle on my Corrado....