Windows/Linux: Burning any old video file to a playable DVD is a bit of a hassle. We've always liked using DVD Flick for tackling the task, but DVDStyler is another great option with a bit more focus on nice menus.
Apps like DVDStyler and DVD Flick work by first transcoding your video files to DVD-friendly MPEG-2 format, then burning the results to your DVD. DVDStyler has pretty excellent support for popular video formats, including AVI, MOV, MP4, MPEG, OGG and WMV, and codecs like MPEG-2, MPEG-4, DivX, Xvid, MP2, MP3 and AC-3. While it doesn't seem to support quite as many as DVD Flick (which handles over 45 file formats and over 60 video codecs), it seems like it covers the most popular options. Everything you'd want to do with DVDStyler is available through simple, user-friendly drag-and-drop, so there's not much to using it other than dragging videos you want to burn into the app, tweaking the WYSIWYG menu editor and burning.
DVDStyler is a free, open-source download for Windows and Linux. Note: DVDStyler will try installing a crapware toolbar, so pay attention during the install process and be sure to opt out.