Directly answering your question of it is difficult to shard a relational database, physically it can be done relatively easily if you have the proper hardware and an Enterpise level database (you need Enterprise edition of SQL Server for instance not the standard version). But to do it correctly requires someone who understands high performance database systems and performance tuning and someone who thoroughly understands your data stucture (you do want related items to end up on the same partition). Your current design may or may not lend itself to partioning without changes. A database designed without the proper fields to do the partitioning on would need them added. Planning what is the best way to partition, designing the partions and testing them can be time consuming even if the actual SQL code to set up the partitions is relatively straighforward.
Lots of large terabyte-size relational databases exist and generally they are partitioned for performance. However, to do this properly requires someone with advanced database skills not only to partition the data but to make sure your queries are properly tuned for performance and that your design will perform well under the required load. A poorly designed data structure on top of hardware that is inadequate on top of badly designed queries (say those with correlated subqueries) will never perform well no matter how you slice the data. Most application developers don't have the skill set to properly design this stuff and then they complain that relational databases aren't fast enough. This is just a sign of incompetence in database design not the actual ability of the database to perform with a large number of users and a huge amount of data. I've seen badly designed and performing websites, does that mean Java or C# can't be used to produced a well-designed site?
If you already have the data in a relational database, it is probably better to hire a database expert to set up and manage your databases for growth that to try to convert to a noSQL solution. Whether you need to partition is irrelevant to the choice to use a key value store. You only want to use those for some specific special cases. For data that needs to be reliable and internally consistent, a key value store is a disaster waiting to happen. Don't forget there is a huge cost associated with converting relational data to a new type of data storage method and new bugs will be introduced, some of them possibly fatal bugs. IF your current databse physically can't handle the projected load (And Access just springs to mind here, you noted mySQL and SQL Server both of which can handle huge databases if properly designed), then it is less risky to convert to a more enterprise type of relational database than to convert ot a Key-value store.
For data that can lose consistency without a huge problem such as social networking sites (it's annoying if they lose your last post but not critical to the business) or search engines (Google isn't going out of business becasue it lost the references to your web site temporarily), then noSQL and key value stores are fine, but you won't find many companies trusting their critical financial data transactions to this type of data store and there's a reason for that. And incidentally using a key-value structure within a relational database will often cause performance issues as they are not optimized for that type of data.
There is a place for both types of database, but they store two very different types of data. It isn't so much about speed (which can be optimized to be excellent for either type of database by someone who actually knows what he or she is doing) as it is about how the data is used and queried and what kind of internal checks for data quality and consistency are necessary. And there is no reason at all why you can't use both in the same project - one for the data that doesn't need to be ATOMIC and one for the transactional data that you need to enforce key relationships for.