$ introduces text style, you will need either \displaystyle or \limits.
(\sum, \int, \lim, … behave in the same manner: Display-style formulas have their super- and subscripts above and below the sign, in text-style formulas they are typeset like normal super- and subscripts.)
If you find both solutions unsatisfying you can define an additional command that has \limitsbuilt in:
\DeclareMathOperator*{\argmin}{argmin}
\DeclareMathOperator*{\argmax}{argmax}
\newcommand*{\argminl}{\argmin\limits}
\newcommand*{\argmaxl}{\argmax\limits}
or with your original macro names having that feature:
\DeclareMathOperator*{\argminOp}{argmin}
\DeclareMathOperator*{\argmaxOp}{argmax}
\newcommand*{\argmin}{\argminOp\limits}
\newcommand*{\argmax}{\argmaxOp\limits}
But than you could just make it without \DeclareMathOperator*:
\newcommand*{\argmin}{\operatornamewithlimits{argmin}\limits}
\newcommand*{\argmax}{\operatornamewithlimits{argmax}\limits}
I have also declared your operators with out the predefined operators \arg and \max as operators are usually in upright font anyway, and then there's no need to re-adjust the space manually (the \!).
Code A (\limits)
\documentclass{book}
\usepackage[chapter]{algorithm}
\usepackage{algorithmic}
\usepackage{amsmath}
\DeclareMathOperator*{\argmin}{argmin}
\DeclareMathOperator*{\argmax}{argmax}
\begin{document}
\begin{algorithm}
\begin{algorithmic}
\STATE some statement here
\WHILE{!stop}
\STATE $s_{i} = \argmin\limits_{p} \| l_{j} - s_{p} \|$
\ENDWHILE
\end{algorithmic}
\end{algorithm}
\end{document}
Code B (\displaystyle)
\documentclass{book}
\usepackage[chapter]{algorithm}
\usepackage{algorithmic}
\usepackage{amsmath}
\DeclareMathOperator*{\argmin}{argmin}
\DeclareMathOperator*{\argmax}{argmax}
\begin{document}
\begin{algorithm}
\begin{algorithmic}
\STATE some statement here
\WHILE{!stop}
\STATE $\displaystyle s_{i} = \argmin_{p} \| l_{j} - s_{p} \|$
\ENDWHILE
\end{algorithmic}
\end{algorithm}
\end{document}
Code C (built in \limits)
\documentclass{book}
\usepackage[chapter]{algorithm}
\usepackage{algorithmic}
\usepackage{amsmath}
\DeclareMathOperator*{\argmin}{argmin}
\DeclareMathOperator*{\argmax}{argmax}
\newcommand*{\argminl}{\argmin\limits}
\newcommand*{\argmaxl}{\argmax\limits}
\begin{document}
\begin{algorithm}
\begin{algorithmic}
\STATE some statement here
\WHILE{!stop}
\STATE $ s_{i} = \argminl_{p} \| l_{j} - s_{p} \|$
\ENDWHILE
\end{algorithmic}
\end{algorithm}
\end{document}
Output

\argand\minrather than just\DeclareMathOperator*{\argmin}{argmin}. – barbara beeton Nov 20 '12 at 15:10