Mark Wallinger is definitely not the first: Jaume Plensa installed a  
huge two part video fountain "Crown Fountain" in Chicago in 2004.  
This work is in the open, unsheltered, and permanent. So much for the  
record, see:

http://en.wikipedia.org/wiki/Millennium_Park

as for discourse: In Hamburg, Germany, there used to be an ambitious  
'art in public spaces' programme (until it was ditched about 5 years  
back by a new conservative government). This programme was financed  
through a percentage in the city's budget, and included not just the  
commissioning of permanent works but also of temporary projects, most  
of which have been documented in books. One internet based project  
"Hamburg Ersatz" by Delbrügge / DeMoll is still online; a public work  
of art. English version button at the bottom of the text links to a  
sister work, the "Copenhagen Substitute"

http://hamburg-ersatz.trmd.de/

One year, the commssioning of projects / works was suspended in  
favour of a series of discoursive events that were investigating  
notions of art and public. Exemplary here is Christian Philipp  
Müller's project "Kunst auf Schritt und Tritt / Public Art Is  
Everywhere" published in 1997 (german / english), an investigation  
into the role of art in a particular part of Hamburg; the publication  
includes essays by, eg., Miwon Kwon who put the specific context into  
a broader international (American) perspective. Other works, though  
not strictly "new media" included the "Open Public Library" by Clegg  
& Guttman which consisted of the installation of three public  
libraries in small electricity boxes, that worked on a 'bring one,  
take one' scheme; the work also included a sociological study by  
students at the University of Lueneburg (nearby Hamburg) which was  
exhibited in the Kunstverein Hamburg during the artists'  
interventions. Within this context I would put any works by Jochen  
Gerz who has worked with ideas of permanence and memory in various  
media, including the internet. Below link has links to a large number  
of his works.

http://www.medienkunstnetz.de/works/berkeley-oracle/

from a UK perspective, I have a problem with the term of "public" in  
relation to the financing of works. A lot of commissions seem to run  
through organizations that specialize in "public art". They team up  
with some developer who is required to put a work of art close to  
their building; and then some abomination is put in place that is  
made by some artist who specializes in "public art". I wonder where  
role of 'public' is. My understanding of public in "art in public  
places" is that it is financed by the public, ie. the councils, the  
cities and villages, and reflects the role of the public and of  
citizenship. The works of art are means of communicating that  
relationship of individual / group and political framework. Yet the  
financial framework of Private Public Partnerships (if this is what  
these organisations are) obscures any relationship with the public  
and becomes a purely financial funding set-up in a particular branch  
of art business.

best

Jorn