Just like to say that I'll choose Perhentian over Redang any day. Firstly because, as everyone has said, its much cheaper (you can get very decent accoms for 20RM/night), its got a better air to it (less touristy, laid-back, without being the party paradise that some of the Thai islands are), and, in my opinion, the diving's just that much better. The good Redang sites like Minimount and Maximount are great, but the others are very run-of-the-mill. On the other hand the average Perhentian site is very pleasant, nothing you'd get bored at, while the good ones - Secret Reef, MV Union Star wreck, T3, Pinnacles, are excellent every time.
My advice would be to go to Perhentian, then when you're there try to do a day trip to Redang. If you have a big enough group, and the 6 of you is enough for this, you can get your shop to arrange one of these if they have a suitable boat to go the distance. Give them a couple day's advance warning. Then when you get there, try to do Minimount and Maximount in particular... the whole trip will take maybe 10 hrs, 8am to 4pm, maybe more if you can negotiate a third dive there. One shop I know for sure does this is Turtle Bay Divers, at
http://www.turtlebaydivers.com, the op I regularly use. By doing this, you'll cover the only Redang sites that are worth seeing.