How to dual encode two sentences to show similarity score
How can I create a dual encoder though? Do I use two different neural
  networks? Or does output just contain one neuron that outputs
  similarity?


You don't need to create two different neural networks (or two different encoders) for it. Whenever you have a symmetric pieces problem, like in your case, its two sentence similarity, you should encode both the sentences using the same encoder and then use cosine similarity. (It can be the similarity of two faces also - just the way FaceNet is expected to be used.)


  we will perform sequential search on whole database by comparing
  cosine similarity (highest similarity vector is picked). But this is
  extremely slow...


You are right, I am assuming you would be using a for/while loop for computing the similarity. In computing the vector similarity of one sentence against a database of thousands or millions, you should make use of a high-performance library like BLAS which would do the same calculations sub-second.

Facebook three years ago came out with a faster matrix library called FAISS. This would reduce your speed drastically.