Table with 4 million records - different size and performance in development and production
Never do shrink database as it increases fragmentation even more. And yes, it looks like sizes are different because of fragmentation, so you have lots of space that stores nothing (half filled pages). This is probably because of incorrect schema design and wrongly chosen clustered indexes. But fragmentation happens on production system and it's good idea to check for it and do index rebuild on a regular basis. 

The error you get might appear of not enough memory so you could try SORT_IN_TEMPDB = ON option. Also consider REORGANIZE option as it is online and even if it fails, it will save all work done prior it fails. But REORGANIZE option just defragments leaf level of an index, not the entire tree.

If it doesn't help, the only way is to recreate database with scripts and fill it with production data but I hope it won't be necessary.