This is a big, complex question, and probably cannot be fully answered in the scope of a single answer.
It's true that full-copy sandbox environments are generally rather expensive, although pricing questions can only be properly answered by your Salesforce account executive.
If you cannot afford a full-copy sandbox, you're stuck with various options for replicating data from Production to your partial-copy or Developer/Developer Pro sandboxes. All of these options have shortcomings.
You can perform one-off loads using the Data Loader. This typically involves a lot of
INDEX/MATCH() work in a spreadsheet application (Excel or LibreOffice; I prefer the latter). It's slow, manual, and error-prone.
For manual and all other types of load besides sandbox copying, you'll likely need to use SF Switch or OwnBackup or a similar tool to disable triggers and other automation during the load process. You may also need to disable lookup field filters if your existing data set is not especially clean or doesn't respect the invariants that your current metadata is enforcing.
You can use the Salesforce DX tree import and export commands. However, based on your broad description of your object model, they may not provide enough depth on their own to support your needs.
Because Summer '18 provides sandbox-from-a-sandbox clone functionality, you can establish a single "master" sandbox, with your full testing set of data included. You can then clone further sandboxes off of that sandbox and refresh them from the master. You'd need to perform code and metadata deploys to your master sandbox to ensure its metadata mirrors production, but without touching the data contents - then your downstream sandboxes will have a clean dataset, but with up-to-date codebases.
Lastly, you can use a third-party AppExchange tool for data replication, such as OwnBackup (the only one I've used). It'd be on you to determine if any specific product meets your replication needs, and you'd be dependent on the vendor for further support and customization.