I went the route of the books you mentioned, "CGI Programming with Perl"
and "Programming the Perl DBI". While both are a bit "thin", I have
found them to be most useful.

The Perl CGI book goes into all sorts of technologies, from
how to use CGI.pm and HTML::Template, all the way to using WDDX and
Javascript in your applications. I found that it is a well rounded book.
It won't make you an expert in everything, but will get you kick
started in a bunch of areas.

I also found the DBI book to be useful, although I haven't had
the time to dig through it as much as the CGI one.

Depending on what you are looking to accomplish, there is also
the book "Official Guide to Programming With Cgi.pm", written by
Lincoln Stein, also the author of the module. While I can't
tell you how good the book is, I'm sure it would get into a lot
of neat nitty gritty if you know what I mean :-)

These two books were also cheap for me, as I was able to convince the company
I work for to purchase them. While they are company property,
I use them both at home and work. YMMV :-)
-Eric