Lowest pixel resolution needed to support Chinese?
8x8: Lowest necessary resolution for Chinese characters

As far as I know, the recognizable lowest resolution for Chinese characters, is about 8x8 pixels. The following paragraphs are rendered by the Special SimSun font's smallest 8x8 bitmap glyphs (Note: "Before Revision" is rendered by the Windows Vista's default simsun.ttc; "After Revision" shows how Special Simsun improves the quality). I believe native speakers are able to read these 8x8 resolution characters within the context, though a few are difficult to be recognized individually.




  "The Special SimSun font is revised based on simsun.ttc and mingliu.ttc contained in Windows Vista: First, it replaces ugly bitmap glyphs of Windows Vista's simsun.ttc with those of Windows XP's, and adds a few other bitmap glyphs; Second, it completes the bitmap glyphs in CJK EXT A (6852 characters), and supports the GB18030 character set (27533 characters) – especially, some low-resolution bitmap glyphs are included so that characters can be rendered in the bitmap way under 6pt–21pt for 96dpi; Finally, all bitmap glyphs are revised one by one, so the rendering quality is improved." — By the author of this font


It would be remiss of me not to mention the 7x7 resolution font: 超宋体 (Super Song) made by 夏夏@bbs.themex.net. However, this font is simplified Chinese only, and we can imagine it will be even more difficult to read than 8x8 resolution characters, so my conclusion for OP's question is "about 8x8".

12x12 would be moderate

The following paragraphs are rendered by the 方正像素12 font with its 12x12 resolution glyphs. Almost every character can be recognized without context. Of course, compared with the 16x16 resolution, it has to lose strokes even for many simplified characters; however, yes, native speakers may feel relaxed to read them now.