Upscale your tiny images and use that instead:
BufferedImage tiny = ImageIO.read(new File("..."));
BufferedImage bigger = new BufferedImage(tiny.getWidth()*10, tiny.getHeight()*10, tiny.getType());
Graphics2D g = bigger.createGraphics();
g.setRenderingHint(RenderingHints.KEY_INTERPOLATION, RenderingHints.VALUE_INTERPOLATION_NEAREST_NEIGHBOR);
g.drawImage(tiny, 0, 0, bigger.getWidth(), bigger.getHeight(), 0, 0, tiny.getWidth(), tiny.getHeight(), null);
Replace the 10 scaling factor by the smallest value that gives acceptable results.
Do the rest of your rendering with high quality interpolation.