For those with no car, the local trail conference (which I assume you are all members of, right? hint hint) has a list of hikes accessible via public transportation. When we first started hiking the area, we found that list to be invaluable in finding new areas.
As for rental cars, we use Zipcar quite a bit. While the rates are relatively high, it sure made sense to go with Zipcar when gas was at $4.00+ (gas is included in the rental fee). With gas cheaper, we price shop more.
The other trick we've learned is to rent cars along the Metro North line if we're going North. The rates are much better than in the city. The penalty is that many places are not open Sundays, so you pay for the car to sit in their lot until Monday when they check it in.
It seems like I spend more time searching for how to get to a place than I do actually planning for the hike.
I'll also add that we went to the Delaware Water Gap on the PA/NJ boarder about a month or so ago and it was wonderful. Tammany is a fun hike and has a great view of the water gap. It's an easy drive along I-80 to the gap. We only did a day-hike, but I hear nothing but good things about Sunfish Pond.
I did a solo overnight in NW Harriman a few weeks ago. I had Bald Rocks shelter to myself (except the inquisitive deer). While the peaks are not exactly high, there are a few trails that follow really nice ridge lines with clear views.
The NYNJTC recently redesigned their webpage. If you can't find hiking partners on BPL, check out the forum on their site. Also, there is a Yahoo! group devoted to hikes in Harriman. People announce trips there nearly every day. I've never been out with them before, but it seems like they have a wide range of hikes. Finally, if you're single, check out Harriman Hikers. They have been around for a long time and do overnights every few weeks it seems.