Australia and other exotic (from the US) trips are great but for your first trip it makes sense to go to one of the mainstream and relatively easy to get to dive destinations with lots of divers in the Caribbean. Get immersed in diving, get practice, and get an idea of what you like. Places such as Bonaire, Curacao, Cozumel, Cayman, Belize, Turks&Caicos, Bay Islands.
Do you think you are more interested in boat or shore diving? Some people like shore diving because of the cost savings, lack of schedule, or because they get seasick on boats. It may be harder to get buddies when shore diving, unless you get lucky and hook up with other lone dive travelers. Some people prefer boat diving, finding it easier to just hop on a boat and be taken to various sites instead of carting gear all over the place. Finding a buddy may be easier on a boat, and there will usually be the option of diving with the divemaster. Some places have lots of shore diving and some have none, and everything in between.
Instabuddies can be a problem sometimes. Another thing you can do is look for organized trips. These might be run by dive shops (local or not), photographers, magazines, or just like minded groups of people such as singledivers.com. Some trips will be advertised on this board. Often there will be other buddy-less divers on these trips so you have an opportunity to pair up with someone compatible and stick with them for the trip.