HPN and SWF pop up as coterminals every now and then, but are usually pretty safe. At times I have found airlines treating EWR differently than JFK/LGA, but that tends to be rare.
BOS isn't too far, and you could always catch the super-cheap Chinatown bus if you are on a strict budget.
PHL would be another fairly close option.
Originally Posted by number_6
Coterminals are considered to be the same city, and your trip ends when you reach a coterminal (EWR in your example). This is a very firm rule. There is a list of coterminals published on each of the airline web sites (sorry, don't have the URLs, but they have all the obvious ones covered and also include some more distant coterminal airports -- this rule is really bulletproof).
Edited to add the best you can do is return to a nearby city like Boston or I think White Plains and Newburgh are not coterminal in NYC (not 100% sure about the last 2, but getting to them would waste a segment). Maybe MCO is a good stopover city for NYC (presumably lots of flights and cheap fares).