The AVI or MKV part isn't important here. AVI and MKV both are just "containers" for video and audio data. What counts is the "codec" inside these containers. The actual video data.
Please read the following for more info: What is a Codec (e.g. DivX?), and how does it differ from a File Format (e.g. MPG)? — it is vital to understand the difference between codecs and containers to grasp the underlying concepts.
The most plausible explanation would be that the 350 MB files use DivX or XviD as encoder, an MPEG-4 Part II codec. These are pretty good, but in terms of quality vs. file-size they are a little inefficient and outdated.
You see, an encoder takes the original video and tries to remove all kinds of redundancy, thereby throwing away information. This is how it reduces file size, but by throwing away information it'll also reduce the visible quality. Various encoders have their own strengths when it comes to deciding what to throw away and how to optimize for human perception, but there's no magic encoder that creates a super tiny file with incredible quality.
The smaller videos you have will probably use x264 as encoder, an h.264 codec. h.264 codecs are much more efficient when it comes to quality vs. file size. They manage to retain quality better at low bit rates and file sizes than most other codecs.
Note however that re-encoing an already encoded file will definitely reduce its file size – which is our first goal –, however it will also drastically reduce its quality. This is called generation loss.
The only way to get small files with good quality is to re-encode the originals — ideally, as a customer, that would mean ripping from Blu-ray discs or direct HDTV signals. So, to repeat, you can't re-encode a 350 MB AVI file (that uses XviD) to a 95 MB MKV file (with x264), without experiencing quality loss. You would need the original "House" Blu-ray disc to do that.
For further reading: