Обратите внимание, что Заказ имеет свойство Customer.Вам не нужно добавлять Заказ клиенту - вы можете сделать это наоборот.Таким образом, вместо создания нового клиента, получите клиента с помощью Linq, а затем добавьте его в свой новый заказ.
using (OrderDatabase ctx = new OrderDatabase())
{
ctx.AddOrder(new Order()
{
OrderQuantity = 2,
OrderDescription = "Widgets",
Customer = ctx.Customers.First<Customer>(c => c.CustomerId == yourId)
});
ctx.SaveChanges();
}