Make Legendre symbols the same size

You can (and should) use \genfrac:

\documentclass{article}
\usepackage{amsmath}

\newcommand{\genlegendre}[4]{%
  \genfrac{(}{)}{}{#1}{#3}{#4}%
  \if\relax\detokenize{#2}\relax\else_{\!#2}\fi
}
\newcommand{\legendre}[3][]{\genlegendre{}{#1}{#2}{#3}}
\newcommand{\dlegendre}[3][]{\genlegendre{0}{#1}{#2}{#3}}
\newcommand{\tlegendre}[3][]{\genlegendre{1}{#1}{#2}{#3}}

\begin{document}

We can use the Legendre symbol $\legendre{\pi}{\theta}$
\[
\legendre[3]{\pi}{\theta} = \legendre[3]{\theta}{\pi}
\]
We can also choose the size
\[
\frac{\dlegendre[2]{\pi}{\theta}+1}{3}
\]
\end{document}

The command \legendre, \dlegendre and \tlegendre act the same as \frac, \dfrac and \tfrac.

The \genfrac command takes six arguments:

1. left delimiter (if empty, no delimiter);
2. right delimiter (if empty, no delimiter);
3. the thickness of the fraction line (if empty, standard thickness);
4. the math style to use (if empty, use the current style); styles are denoted by 0 (display style), 1 (text style), 2 (script style), 3 (scriptscript style);
5. the numerator;
6. the denominator.

Thus we get \legendre from \genlegendre by passing nothing as fourth argument to \genfrac, \dlegendre by passing 0.

The \if\relax\detokenize{#1}\relax trick is for avoiding an empty subscript that would generate \scriptspace nonetheless.

A solution with \mathstrut and the mleftright package:

\documentclass{article}
\usepackage[utf8]{inputenc}%
\usepackage{mathtools}
\usepackage{mleftright} 
\newcommand{\Leg}[3][]{\mleft(\frac{#2\mathstrut}{#3}\mright)_{\mkern-6mu#1}} 

\begin{document}

 \[ \Leg{\pi }{\sigma}\quad \Leg[3]{\pi }{\theta}\quad \Leg{\theta}{\pi} \]

\end{document}

I've changed your syntax a bit: The optional argument now is a size command and your index is mandatory. Just play around with the sizes you like.

The problem with your command is that you automatically apply auto-sizing (left and right), which will not result in same output if different input is given (especially with different sizes).

Btw: You should use \[...\] instead of the $$ syntax.

\documentclass{article}
\usepackage{amsmath}
\newcommand{\Leg}[4][big]{\csname #1l\endcsname(\frac{#3}{#4}\csname#1r\endcsname)_{#2}}

\begin{document}
\[
    \Leg[Bigg]{3}{\pi}{\theta} = \Leg[Bigg]{3}{\theta}{\pi}
\]
\[
    \Leg{3}{\pi}{\theta} = \Leg{3}{\theta}{\pi}
\]
\end{document}