Check out my presentation for SQL PASS on Effective Data Warehouse Storage Patterns.
http://craftydba.com/?page_id=880
The presentation reviews the following techniques to fix your woes. It has working code for a 1.2 M row database.
Coverage:
1 – What is horizontal partitioning?
2 – Database sharding for daily information.
3 – Working with files and file groups.
3 – Partitioned views for performance.
4 – Table and Index partitions.
5 – Row Data Compression.
6 – Page Data Compression.
7 – Programming a sliding window.
8 – What are Federations in Azure SQL?
As for which way to go, it is up to you.
Both sharding and partitioned views can be done with the Standard version of SQL Server.
Data compression and table partition are available in the Enterprise version of SQL Server.
Since you are building the warehouse from scratch, you can change the data types to eke out space.
I was able to re-organize a 4 TB database into 500 GB using compression and partitioning.
In summary, both DATES and INTEGERS are good candidates for partition keys.
In my own warehouse, a date dimension mapped a date to an integer.
Play around in a test environment to get a feel on how a real rebuild will work.
Good luck.