We really can't know. you have to provide screenshots or a YouTube reference as well as your exact render settings, comp settings, source of the footages (no, just saying it's an MP4 file is not good enough) and exact specs and all the other juicy details...
You have to scale up the smaller layer. Since it's in a 4x3 screen ratio, and the comp is a 16x9 screen ratio, you'll have to scale it up to fit from side to side. You'll lose the top & bottom of this layer, and you'll have to position it vertically until it looks best.
And with all that scaling up, "best" is a very vague term.
*** 1920x1080 and 640x480
Your instinct to down covert your 1920x1080 to 640x480 is a good one as far as picture quality is concerned; however, it will leave you with a 640x480 edited master (as long as a low resolution file is okay, you’re good).
Set your Comp to 640x480 and then scale your 1920x1080 layer to fit the Comp height (Layer > Transform > Fit to Comp Height). Note: This will crop the left and right side of your picture. If your 16x9 picture was designed for “Center Cut” (common in broadcast, cable and DVD-Video), then you’re okay. If the picture was not designed for Center Cut, then you may need to look at other approaches to conform your 16x9 to 4x3.
You could split the difference: Work in a 1280x720 Comp in AE. Scale your 1920x1080 source footage down to 1280x720 (Layer > Transform > Fit to Comp). Scale your 640x480 source footage up to either fit the Comp height (this will “pillar box” your picture) or to fit the Comp width (this crop the top and bottom of your picture). If your AE is up to date (AE 12.1), scale the 640x480 footage up by using the Effect “Detail Preserving Upscale” (new in version 12.1). If you’re using AE 12.0, use the Scale property (Layer > Transform > Fit to Comp Height or Fit to Comp Width) and be sure to set the Layer Quality switch to Bicubic (Layer > Quality > Bicubic). If you’re using AE CS6 or older, just leave the Layer Quality switch at “Best”.
*** wierd artifacts and noise in rendered files
This is most likely a result of a highly compressed mp4 file that might have very good picture quality as is, but completely fall apart when used as source footage.
Try transcoding your mp4 file to settings that are good for editing in Adobe Media Encoder (it should have installed with AE). Of course, “good for editing” is often hardware dependant. Without knowing more about your system, I’d suggest going with a QuickTime movie using Photo-JPEG compression at best (the “at best” is _really_ important). This file will take up a lot of disc space and have a higher sustained data transfer rate than your mp4 file. However, if the picture holds up to the conversion to a Photo-JPEG QuickTime, then it should hold up to being rendered in AE to your final movie. If the movie still falls part, you’re not out of options but things get a little more challenging. You could use screen-recording software to capture the desktop playback of your mp4 file and save to something that will hold up to editing or you could patch the video out of your computer (if present) to the video input of another device (like HDMI out to HDMI in) and capture that to something that is good for editing.