A fish sandwich is a sandwich made with fish as the filling between the pieces of bread. In English we can make things very compact, to get "fish sandwich." However, in Spanish, this trick is not available to us, so we need to say "sandwich de pescado" (literally, sandwich of fish). Here are some more examples:
corte de luz (power outage -- more literally: outage of power)
tablas de multiplicación (multiplication tables -- more literally: tables of multiplication facts)
cepillo de dientes (tooth brush -- more literally: brush of teeth)
The other construction might be confusing you because español can be an adjective, but also a noun. In your restaurant example, it is being used as an adjective. This is similar to:
Now, here are some phrases that include español as an adjective:
and as a noun: