Of course, it's not impossible (or hard) to do the same on a Windows desktop. It's just far more convenient on a Linux desktop with the vast number of tools available.
You could do this using bash, Perl, Python, and Ruby just to name a few. It's a topic that's been blogged to death, I'm sure. I'm just a Linux hobbyist who's also interested in Python scripting so here's my (rather simplistic) version for renaming video files.
vids = glob.glob("*.avi")
start = 1
ep = range(start, start + len(vids) + 1)
name = "foo"
for f,e in zip(sorted(vids), ep):
print "Rename %s to" % f, \
"%s - %02d.avi" % (name, e)
shutil.move(f, "%s - %02d.avi" % (name, e))
The script finds all avi files in the current directory and renames them "foo - 01.avi", "foo - 02.avi" and so on. Simply replace foo with the appropriate filename. For renaming mkv, ogm, mp4 or any other video formats, simply replace the file extension with the appropriate one.
There's more than one way to do this, of course. It's really about how powerful/flexible you want to make it and how much effort you think is appropriate. My script doesn't even bother checking if the target filename is already in use so be sure to either manually check this, or edit the script to perform the check. You've been forewarned.
The Python Tutorial
Dive Into Python