I'm afraid I disagree with Trum48 and so do most of the people on TripAdvisor. Put Sabah into the search on their site & read what people have to say about the Rasa Ria.
The diving takes placeat Sipidan on the East coast (opp to KK) and Sepilok is also that side + the river trips to Sukau. You could split your holiday between both sides of the island or settle for a tour.
http://www.goldendays.co.uk/Tours.html
These people have a couple of dive/wildlife/beach tours that have a good itinerary.and as the tours are usually based on 2 people you can make changes to suit yourself.
These people do tailormade dive/wildlife holidays in Borneo
http://www.planetdive.co.uk/destinations/borne o/borneo.asp
These people - Reef and Rainforest also do tailor made trips including diving and could give ideas & prices
http://www.familytours.co.uk/cgi/country.asp?r egion=4&country=11
Best thing to do is google Borneo and read about the various places in Sabah and get an idea of what you want to do then get quotes or look at some of the existing tours and ask the company if they can arrange some diving at Sipidan instead of -for example - going to see the Turtles which a lot of trips include.
Good luck!