It wasn't about speed of execution, but expressiveness when coding. Later on they even added proper type system support.
Common operations were things like map/project, extend, filter, join, collect-by-key / expand, etc.
Just as Codd pointed out in his original papers, relations allow you to not have to make a choice about a hierarchy for your data.
Using key-value store like a hash-table in your program, or the much vaunted has-a relationship between objects would force you to make these choices. Thus making interacting with the data awkward for all but one access pattern.
Relations work best when your program is written in a style that deals largely in immutable data. (What we call 'purely functional', but people in dysfunctional languages have also picked up on the advantages recently.)
Or, alternatively, make it really painful when you do actually need to query hierarchies, along the lines of "give me all the tuples above this one in the hierarchy".