Here are the results from the second method. This method works in a different way from method one.
Method one works by placing some tiles down at for each tile size and continuing on until the image is full.
This method fills the entire image at each tile size. At each tile size, a full mosaic is created using only tiles of that specific size. Tiles are optimally placed using the munkres algorithm. After a full mosaic is created, it is compared to the mosaic that has already been computed (which is empty on the first size). If a square from the newly computed mosaic is better than the square (i.e. is closer to the target image) then it replaces that square in our ever-bettering mosaic. This process is repeated for all sizes.
This method certainly looks less grid-like than the other method, which is a plus. In terms of similarity to target images, I would say that both methods are quite similar (although this has not been tested scientifically). However, this method produces less full tile images since they are constantly being covered up at each level. This means the tiles are on the whole less intelligible and interesting.