how difficult would it be to build a simple (say 2-3 choices, each
with a couple of further subchoices) graphical interface in a linux
based handheld device with a graphical lcd? Just need to have some
rough idea of the difficulty level as compared to having such an
inteface in a win ce based system and also whether it is 'realistic'
at all.

Check out WAP for a hint. What they use in Cell Phones may be close to
what you might want/need.

Otherwise, lynx/links or text browser might still be overkill...

linux support a lot more PDA's than win ce.

Besides, to create GUIs with win ce, or you buy the developers suite
or you learn how to code html/javascript or vbscript.

with linux, there's tons of programs that let's you create GUIs just
clicking the mouse (simplier than visual basic or delphi). and the
SAME code you develop on your linux desktop can be sent to your PDA.
With win ce you would have to recompile and i don't know how to do
that.

if you use tk ou gtk, i belive your program can be made in 5 to 20
lines. I would call that easy :)
besides, there's lot of info in google. just search for "tk|gtk sample code"

The html+script option in win ce isn't very bad, unless your program
need to write something into disk, then the browser where you will run
your "code" within may deny access to some files...