Given a conic problem $$\min \{c^\top x \mid Ax \succeq_\mathit{C} b\}$$ for an arbitrary cone $C$, how can I construct the dual to the problem?
Moreover, in Linear Programming one constructs the dual with the intention of finding a valid (in fact the best) lower bound on $x^*=\min \{c^\top x \mid Ax \geq b\}$. Is there a similar intuition in the case of conic duality?
$\newcommand{\Rbar}{\overline{\mathbb{R}}}\newcommand{\R}{\mathbb{R}}\newcommand{\minimize}{\operatorname{Minimize}}$Another way to derive the dual for any convex problem is to use Fenchel duality.
Define $\Rbar=\R\cup \{+\infty\}$. A function $f:\R^n\to\Rbar$ is called proper if there is an $x\in\R^n$ such that $f(x) < \infty$. Given a nonempty convex set $C\subseteq \R^n$, define
$$ \delta_C(x) = \begin{cases} 0,&\text{if } x \in C\\ \infty,&\text{if } x \notin C \end{cases} $$
Consider the following optimization problem
$$ \mathbb{P}: \minimize_{x\in\R^n} f(x) + g(Ax) $$
where $f:\R^n\to\Rbar$, $g:\R^m\to\Rbar$ are proper, convex, lower semicontinuous functions and $A\in\R^{m\times n}$.
The convex conjugate of a proper convex function $f:\R^n\to\Rbar$ is defined as the function $f^*:\R^n\to\Rbar$ with
$$ f^*(y) = \sup_x x^\top y - f(x) $$
The Fenchel dual of problem $\mathbb{P}$ is the following convex optimization problem
$$ \minimize_y f^*(-A^\top y) + g^*(y). $$
Define $f(x) = c^\top x$, $g(z) = \delta_{\mathcal{K}}(b-z)$, where $\mathcal{K}$ is a closed convex cone. Then, the conic problem
$$ \begin{align} \minimize_x\ & c^\top x\\ \text{subject to }& b - Ax \in \mathcal{K} \end{align} $$
can be written as
$$ \mathbb{P}: \minimize_{x\in\R^n} f(x) + g(Ax) $$
The convex conjugates of $f$ and $g$ are $f^*(v) = \delta_{\{c\}}(v)$ and $g^*(y) = b^\top y + \delta_{\mathcal{K}^*}(y)$, where $\mathcal{K}^*$ is the dual cone of $\mathcal{K}$. This means that the Fenchel dual problem is
$$ \begin{align} \mathbb{D}: \minimize_y\ & b^\top y\\ \text{subject to }& y \in \mathcal{K}^* \\ &A^\top y + c = 0 \end{align} $$
Note: The inclusion $b-Ax \in \mathcal{K}$ in the primal problem is often written as $b - Ax \succeq_{\mathcal{K}} 0$.
In Linear Programming (LP) one chooses a vector $\lambda \geq 0$ to obtain $\lambda^\top Ax \geq \lambda^\top b$ and whenever we find such a $\lambda \geq 0$ with $A^\top\lambda =c$ we obtain a lower bound $b^\top \lambda$ for our linear programming problem.
In conic programming we also search for vectors $\lambda$ such that $\lambda^\top Ax \geq \lambda^Tb$ follows from the conic inequalities $Ax \succeq_C b$. However, the question arises which vectors $\lambda$ we can choose such that $\lambda^\top Ax \geq \lambda^\top b$ follows from $Ax \succeq_C b$. In LP these were the vectors $\lambda$ with $\lambda \geq 0$. In the conic case it turns out that the vectors $\lambda$ we are looking for are those from the polar cone $C^*$, which is defined as $$C^*:= \{\lambda \in \mathbb{R}^n: \lambda^\top x \geq 0\quad\forall x \in C\}. $$
With this we arrive at the following dual to our conic programme: $$\max \left\{b^\top \lambda \mid A^\top\lambda=c, \lambda \succeq_{C^*} 0\right\}.$$ The optimal dual value is a lower bound on the optimal value of the primal problem. However, one has to note that strong duality (i.e. both optimal values are equal to each other) only holds when both the primal and the dual problem are strictly feasible, which is a difference to LP!
Succinct and (freely) accessible references, which include general "theory". Also, solved examples,. for instance for Second Order Cones (SOCP) and Linear Semidefinite cones (LMI, i.e., Linear SDP):
Chapter 8 "Duality in conic optimization" in "MOSEK Modeling Cookbook" .
Section 5.9 "Generalized inequalities" in "Convex Optimization" by Boyd and Vandenberghe
