A free, cross-platform solution with FFmpeg, which does bitstream copy and therefore doesn't take more than a few seconds, even for large files:
ffmpeg -i input.mp4 -i subtitles.srt -c:s mov_text -c:v copy -c:a copy output.mp4
This works for MP4. Be aware that some subtitle formats might not automatically be compatible with the chosen output formats, so you have to change the codec after
MP4: Use the
mov_text subtitle codec (as in the example above), which implements MPEG-4 Part 17.
ass. MKV does not support
AVI: Very problematic with embedded subtitles. In theory they support SubRip and SSA/ASS subtitles, but only through third party software.
See Wikipedia for a list of containers and their supported subtitle formats.
Using dedicated video encoding programs such as Handbrake will re-encode your video, which reduces its quality and could take you hours to encode – this is why you should check whether the tools support copying the video and audio bitstreams.