As per Vlad's answer, the Dependency API is now GA in Spring '20 (v48.0).
Clarification provided by Vladimir Gerasimov about the current Winter '20 Beta functionality:
Apologies for the confusion. Since Dependency API is currently in beta, it's only available in sandboxes.
I think they way it's documented in our release notes is a bit confusing as it says:
Where: This change applies to Lightning Experience, Salesforce Classic, and all versions of the Salesforce app in Professional, Enterprise, Performance, Unlimited, and Developer editions, sandboxes only.
It's currently not supported in production DE orgs. Good news are that we are planning to expand this beta into production in the next release.
I tested it in a Sandbox (cs93) with the developer console. It seemed to be enabled.

The same SOQL query Select Id from MetadataComponentDependency
in a production org produced a GACK for me... so that is something I'll follow up on.
[object Object]: An unexpected error occurred. Please include this ErrorId if you contact support: 1691316497-63528 (-541748943)
On NA87 I got the same error message you did:
DEPENDENCY_API_UNSUPPORTED_EXCEPTION
[object Object]: Dependency API is not enabled

The release notes say:
Where: This change applies to Lightning Experience, Salesforce Classic, and all versions of the Salesforce app in Professional, Enterprise, Performance, Unlimited, and Developer editions, sandboxes only.
So I'd expect it to work in a production org. I'll message the PM to see what is going on.