From someone who has taken both courses and become both levels, I can say with all honesty that it doesn't hurt to take either/both.
If you find the right Critical Care course, you will be taking an abbreviated paramedic course. I took my CC in Utica, and under the direction of that program I was able to take my paramedic without taking any new notes. Instead while attending my medic program I actually was able to sit and listen to the instructor and form more thought-provoking and important questions.
In the instance of courses, I will admit I feel I took more, clinical wise, from my CC course than medic. In CC, I was required to attend ER time, Cath Lab time, L&D Time, and MedCon time, whereas with my medic class I was only required to do ER time, OR (tube) time(2 tubes) and MD shadow (one shift). Now as for portability, paramedic is the way to go because as many pointed out NY's CC, or, as it used to be known, Level 3, is not honored anywhere else (PS: there are technically 5 levels in NY: EMR, EMT, AEMT, CC, and Paramedic, which all had different titles pre-National Standards).
That being said it is up to you, your bank/financial aid, your time, and where you see yourself in three years or less. It doesn't hurt to take CC, learn from that, and take medic to build on the knowledge CC gave you.