I have a large data 40GB SQL DB that I would like to delete all the data from all the tables, hence my questions: How does one delete data from an SQL Database and Maintaining Referential Integrity+constraints?
It depends.
If you want to delete all the data from all the tables you are better off disabling the constraints, truncating the tables, and then re-enabling the constraints.
If you are just deleting some records you need to delete the child records first and then the parents as @dan-bracuk said. Alternatively if you have cascading delete set up you can start at the parent.
If you are deleting many, many records you may still be better off disabling the constraints if you can limit other activity on the tables for the duration.
If you are replicating the tables then you may have some other considerations.