DVDs that you play in a DVD player do not have mp4's on them they have .vob files. It sounds like you have just burned an .mp4 onto a DVD and expected it to work in a DVD player because it's on a DVD. Unfortunately that's not the way it works, a DVD player will usually only read a certain format of video and it has to be laid out in a very specific way on the disc. When it is in the correct format it is called a video DVD when it is just an mp4 file or other files (documents or whatever) then it is called a data DVD. Depending on the length of the movie you can probably fit the whole thing onto a dvd5 (single layer) without losing quality but you need to do it through a program like nero (windows) or toast (mac). Select the option that allows you to make a video DVD and the program (assuming it has the correct codecs to be able to read your video file) will create the vob files for you and arrange them on the disk in the correct way.
EDIT: Lossless (no loss of quality) conversion is possible, I do it every day. If you are coming from an HD file though then it will lose quality going to SD (standard definition), or if the video is particularly long then the 'bitrate' (amount of data required to make a second of video) will have to be reduced and you will lose quality. Part of the problem you will find is that most SD videos on the internet are 525i/p at best whereas a UK DVD player will e 625i... The video's may well look better on your computer screen than it will on your TV set (even if you were using the TV set as a monitor for the computer) because of how much better the processing is in a computer graphics card than on a TV set. Either way, you need to download Nero or Toast or some other 3rd party software.
I'm a tech at a the biggest independent post production company in the UK.