Worked there in the mid-90s and the paper was a fairly pleasant place. Most of the people were very nice and easy to work for, and the pay, at the time, wasn't bad for a paper its size in the middle of nowhere.
I was a page designer and copy editor on the news side when I was there and helped out a lot with Friday Night Football. The former sports editor, Rich Croome, is a heck of a great guy but is now at the Bryan-College Station Eagle. His assistant took over for him and I believe is still there as SE. I found him to be a perfectly friendly, professional guy, but there was a prickly side to his personality, too.
The paper itself isn't too bad, but be aware that Victoria is literally in the middle of nowhere. It's about two hours to Corpus Christi and San Antonio, but the drive seems to last forever. For a town of about 60,000, there was NOTHING to do (unless hanging out at Wal-Mart is your idea of fun).
Like I said, that was some time ago, and I'm sure the town has probably improved since then. When I was there, I liked my job but couldn't wait to get out of Victoria.
As far as an upgrade from some of the papers you mentioned, I can't say for sure, but certainly it's a better place to cover sports than the Laredo paper. Denton's a much better location, but then you have that whole Belo thing to worry about. Don't know anything about Waco.