There are a couple of different bits of the philosophy of how we use oracles that we need to touch on here:
when we use an oracle, it's often trying to make some claims about how fast the algorithm would run if we had such an oracle. In a sense, it doesn't really matter if you can build such a device or not. Is it unfair to give a quantum computer access to a magical device? What we're comparing it to is a classical computer with access to (more or less*) the same magical device. So long as the two are compared on as equal a footing as possible, that's all that matters.
the value of an oracle is not usually about how magical it is or not. All the standard ones in quantum computing are very non-magical: they're just classical function evaluations which are easily constructed. Instead, the value of the oracle is to put you in a straight jacket and say "you must solve the problem like this..", so that you can make conclusions "when I solve the problem like this, quantum is faster than classical by some factor ...". Of course, in the real world, you can solve the problem in whatever way you want. Generally, the oracles are designed to replicate they way we would expect to do the computation in reality, but we cannot generally prove there isn't a better way.
As for the example of Deutsch's algorithm, your oracle has to have two bits of input ($x,y$) and two bits of output ($x,y\oplus f(x)$) for some function $f(x)$. We need to examples, a constant function and a balanced function. For the constant function, let's assume that $f(0)=f(1)=0$. Then the output is $x,y$. In other words, exactly the same as the input. This "magic" is just two quantum wires.
For the balanced function, let's take $f(x)=x$. Then all we have to do is apply a controlled-not, controlled off the $x$ qubit and targeting the $y$ qubit.
*The quantum and classical oracles can be defined to behave in exactly the same way on classical inputs, i.e. $(x,y)\rightarrow (x,y\oplus f(x))$. Of course, the quantum oracle is a little different as it has to also act on superpositions of inputs. Not everyone feels like this makes a fair comparison.
