Marbelous, 168 bytes
This answer only works up to 255x255, not 1000x1000, due to limitations of the Marbelous language. I'm working on a 32-bit library, but it's not going to be ready any time soon.
Input is provided as two command line parameters or function parameters to the main board.
@2@3}1@0
SLEL//>0\/
@3@1}0--
}1&0@0/\&0
@1/\@2}1\/
:SL
..}0@0
&0/\>0&0
EN..--\/
{0@0/\ES
:EL
..@0
..>0EN
}0--\/
@0/\EX
:EX
}0
\/3D3D3D3D
:ES
}0
\/3D202020
:EN
}0
{03D0A
Pseudocode:
MB(H,W):
EL(W)
for 1..H:
SL(W)
EL(W)
EL(W):
for 1..W:
EX()
EN()
SL(W):
for 1..W:
ES()
EN()
EX():
print "===="
ES():
print "= "
EN():
print "=\n"