I struggle with this all the time. Data driven tests are awesome because you write so little code. But the code is often abstract and the data is long and hard to read.
I have never been a big fan of Cucumber either and I'm not convinced its more readable -- isn't it just more verbose? Interesting point about it being language agnostic though.
I guess I don't have a better solution to contribute. Just wanted to say yeah I have that problem too.