Automatic conversion/encode video for Video On Demand streaming
For a server, you definitely want ffmpeg. I would also strongly recommend compiling it yourself (those are Ubuntu instructions, but should work for Debian as well AFAIK) - the best AAC encoder available for ffmpeg (libfdk_aac) cannot be redistributed alongside x264 (because of the GPL), and the version of ffmpeg in the repositories is probably too old for some of the things I'm going to list here.
MP4
To convert an arbitrary video to an MP4 using libx264 and libfdk_aac:
ffmpeg -i input.avi -c:v libx264 -crf 24 -preset veryfast \
-ac 2 -c:a libfdk_aac -vbr 3 -movflags faststart output.mp4

Control the quality of the video with -crf: a lower number is better quality, but larger file. 18 is visually lossless under most circumstances, and 24 should be more than good enough for online streaming. Use a -preset to control the speed/size of the video: a slower preset means a smaller file (the presets are ultrafast, superfast, veryfast, faster, fast, medium, slow, and slower). See here for more detail.
Control the quality of the audio with -vbr: the scale is 1-5, where 5 is best quality. Actually, even a vbr of 1 should be good enough for your purposes. See here for more detail. -ac 2 means that ffmpeg will output 2 audio channels, mixing down if necessary; you only really need to use it if you think people will send in 5.1 surround sound audio or something.
-movflags faststart is required for internet MP4 video.
WEBM
.webm is a little more complicated. libvpx (the VP8 encoder) should have a crf mode that will work in a similar way to x264's, but it is currently broken. Unfortunately, you'll have to target a bit rate instead. For standard definition, 1000kb/s should give very good quality (in fact, that is probably overkill). For full 1080p HD, about 5000kb/s will give really good quality (again, you can probably go lower - try it out and see). About 2200kb/s should do it for 720p.
ffmpeg -i input.avi -c:v libvpx -b:v 1000k \
-c:a libvorbis -q:a 4 -ac 2 output.webm

NOTE - make sure you use libvorbis (the xiph.org encoder lib), NOT vorbis (the inferior internal ffmpeg encoder). Set the quality with -q:a: the range is -1-10, where 10 is best quality, and 5 is indistinguishable from an original CD. 3 or 4 should be adequate for online streaming purposes.
Subtitles &amp; scale video
To hardcode subtitles, you have to first extract them from the original file, then use either the ass filter or the subtitles filter to encode them. Using the subtitles filter:
ffmpeg -i input.mkv -map 0:s:0 -c:s ass subtitle.ass
ffmpeg -i input.mkv -filter:v 'subtitles=subtitle.ass' \
-c:v libx264 -crf 24 -preset veryfast \
-c:a libfdk_aac -vbr 3 -movflags faststart output.mp4 \
-filter:v 'subtitles=subtitle.ass' \
-c:v libvpx -b:v 1000k \
-c:a libvorbid -q:a 4 output.webm

To scale videos, use the scale filter. -1:480 means 'for the width, keep the input aspect ratio, and scale the height to 480'.
ffmpeg -i input.avi -filter:v 'scale=-1:480' \
-c:v libx264 -crf 24 -preset veryfast \
-c:a libfdk_aac -vbr 3 -movflags faststart output.mp4 \
-filter:v 'scale:-1:480' \
-c:v libvpx -b:v 1000k \
-c:a libvorbid -q:a 4 output.webm

You can combine the scale and subtitle filters like so:
ffmpeg -i input.mkv -filter:v 'scale=-1:480,subtitles=subtitle.ass' \
-c:v libx264 -crf 24 -preset veryfast \
-c:a libfdk_aac -vbr 3 -movflags faststart output.mp4 \
-filter:v 'scale:-1:480,subtitles=subtitle.ass' \
-c:v libvpx -b:v 1000k \
-c:a libvorbid -q:a 4 output.webm

You'd probably want to use a bash script to detect the input height and test the existence of subtitles; I'd personally use mediainfo to find that information, it's pretty amenable to regex.
That should be enough to get you going.