Which of these simple data structures is most efficient when implementing a Dequeue?
We need to clearly separate interface interfaces (abstract data types) from implementation. You talk about implementing a deque, an ADT, in terms of a stack or queue, but those are themselves ADTs. We need to be talking about concrete implementations.

So here's the answer (drumroll please): use a doubly-linked list. All the operations you mentioned are now $O(1)$.