A reorganise-and-shrink is never recommended really.
If you can take the apps the database is serving offline, you can speed up the process and reduce index fragmentation by removing all non-clustered indexes (which may mean dropping foreign key constraints that rely on non-clustered indexes) before the shrink (this will mean there is less data to be moved around as only the data pages will be shuffled not the now non-existent index pages, speeding up the process) then recreate all the indexes and keys.
Recreating the indexes after the shrink means they should not be significantly fragmented, and having them gone during the shrink means rebuilding them won't leave many small "holes" in the page allocation within the files that may invite fragmentation later.
Another option if you can offline the applications is to migrate all the data to a fresh database of the same structure. If your build process is solid you should be able to build that blank DB quickly, if not create one from the current DB (restore a backup of the current one, truncate/delete all the contents in the tables and perform a full shrink).
You might still want to drop all the indexes in the destination and recreate them afterwards as this can be a lot more efficient when changing a lot of the indexed data (100% of it in this case). To speed up the copy process, have the datafile(s) of the destination database on different physical drives to the source (unless you are using SSDs in which case you don't need to care about reducing head movements), you can move them to the source location when you are done.
Also, if creating the destination as new (rather than by blanking a copy of the source) create it with an initial size that will contain all the current data plus some months worth of growth - that will make the data copy a little faster again as it won't be allocating new space every now and again throughout the process.
This might be better than using shrink because migrating the data to a fresh database replicates the intended action of the shrink operation, but potentially with far less fragmentation (which is the unintended consequence of a reorganise-and-shrink). A shrink simply takes blocks from near the end of the file and puts them in the first space nearer the beginning making no effort to keep related data together.
I suspect the result will be more efficient space-wise too as there is likely to be less part-used pages afterwards. A shrink will just move part-used pages around, moving the data is more likely to result in full pages especially if you insert into the destination in the order of a table's clustered key/index (where a table has one) and create other indexes after the data has all migrated.
Another option that is a little more in-place than migrating to a new DB, is to create a new filegroup and migrate all the data to that as discussed in https://stackoverflow.com/a/2438060/114292 - once all the data and non-clustered indexes are moved the file(s) of the base filegroup can then be shrunk to a very small size as they'll be near empty and the new filegroup should be pretty organised space-wise.
Of course if you can't take the apps offline at all, just performing a shrink is your only option so if you really need to reclaim the space go with that. Depending on your data, access patterns, common working set size, how much RAM the server has, and so forth, the extra internal fragmentation may not be all that significant in the end.
For the copy operation, either SSIS or base T-SQL would work just as well (the SSIS option might be less efficient, but potentially easier to maintain later). If you create the FK relationships at the end along with the indexes you can do a simple "for each table, copy" in either case. Of course for a one-off, a shrink+reorganise is probably fine too but I just like to scare people into never considering regular shrinks! (I've known people schedule them daily).
A further option for copying to a new database to effectively shrink and reorganise the data, that wasn't common away from the nascent Azure SQL at the time this question was originally asked, is to export the whole thing to a bacpac and restore. The restore creates the DB schema, bulk-loads the data, then recreates the non-clustered indexes. It may take longer than the approaches mentioned above but requires much less manual intervention or scripting on your part, so you can be more confident that it'll just work.
Updating for 2023: with modern storage systems mostly based on solid-state devices with large amounts of RAM for further caching (cache on the storage device, buffer pool in SQL itself), fragmentation in terms of page locations is a lot less of a concern that is once might have been and this may change the balance of recommendations. Fragmentation in terms of having a great many part-used pages is still something to think about (you'll use more of that buffer pool for the same data and need more IO to read or update the same amount of data) and is only fixed by index rebuilds not reorganisation, as is having a lot of free space due to deleted data (the original issue in this question). With this in mind a one-off shrink is much easier to recommend these days.