I don't think small internal storage will cause lagginess, if small RAM then yes.
4" screen ok? Got...
-LG optimus 2X(laggy on stock ROM, custom ROM ok)
-Samsung galaxy S plus (not many custom ROMS available I think)
-Motorola Atrix (might not get ICS update)
-top up and get HTC sensation @ around 1.5k (4.3" screen)
-Google nexus S (if u can find 1 ori set)
-HTC incredible S (sense UI might slow the phone down a bit)
-SE xperia play
All above are 4" screen except HTC sensation, arc S I think is 4.2". If u insist on arc S, go ahead...quite a good choice

edit: Sorry, forgot 1 big 1...HTC desire HD. 4.3" screen @ around arc S price
hmm~ htc desire HD sounds interesting~ will go to the shop and check out the phones~
it's my first smartphone and i don't really know how to check whether its good or not~